A295511 -id:A295511

The OEIS is supported by the many generous donors to the OEIS Foundation.

Search: a295511 -id:a295511

Displaying 1-4 of 4 results found.

page 1

A295512

The Euclid tree with root 1 encoded by semiprimes, read across levels.

+0
4

4, -6, 6, -21, 35, -35, 21, -10, 221, -77, 55, -55, 77, -221, 10, -33, 46513, -493, 377, -119, 187, -1333, 559, -559, 1333, -187, 119, -377, 493, -46513, 33, -14, 143, -209, 629, -14527, 2881, -1189, 533, -161, 391, -15229, 2449, -2263, 3139, -1073, 95, -95

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

The Euclid tree with root 1 is A295515 (sometimes called Calkin-Wilf tree).

For a positive rational r we use the Schinzel-Sierpiński encoding r -> [p, q] as described in A295511 and encode r as sgn*p*q where sgn is -1 if r < 1, else +1.

Apart from a(1) all terms are squarefree.

REFERENCES

E. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232.

LINKS

Table of n, a(n) for n=1..48.

N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.

Matthew M. Conroy, A sequence related to a conjecture of Schinzel, J. Integ. Seqs. Vol. 4 (2001), #01.1.7.

P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. I., J. Reine Angew. Math. 463 (1995), 169-216.

P. D. T. A. Elliott, The multiplicative group of rationals generated by the shifted primes. II. J. Reine Angew. Math. 519 (2000), 59-71.

Peter Luschny, The Schinzel-Sierpiński conjecture and the Calkin-Wilf tree.

A. Malter, D. Schleicher, D. Zagier, New looks at old number theory, Amer. Math. Monthly, 120(3), 2013, pp. 243-264.

A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arithmetica 4 (1958), 185-208; erratum 5 (1958) p. 259.

EXAMPLE

The tree starts:

-6 6

-21 35 -35 21

-10 221 -77 55 -55 77 -221 10

MAPLE

EuclidTree := proc(n) local k, DijkstraFusc;

DijkstraFusc := proc(m) option remember; local a, b, n; a := 1; b := 0; n := m;

while n > 0 do if type(n, odd) then b := a+b else a := a+b fi; n := iquo(n, 2) od; b end:

seq(DijkstraFusc(k)/DijkstraFusc(k+1), k=2^(n-1)..2^n-1) end:

SchinzelSierpinski := proc(l) local a, b, r, p, q, sgn;

a := numer(l); b := denom(l); q := 2; sgn := `if`(a < b, -1, 1);

while q < 1000000000 do r := a*(q - 1); if r mod b = 0 then p := r/b + 1;

if isprime(p) then return(sgn*p*q) fi fi; q := nextprime(q); od;

print("Search limit reached!", a, b) end:

Tree := level -> seq(SchinzelSierpinski(l), l=EuclidTree(level)): seq(Tree(n), n=1..6);

CROSSREFS

Cf. A294442, A295511, A295515.

KEYWORD

sign,tabf

AUTHOR

Peter Luschny, Nov 23 2017

STATUS

approved

A295515

The Euclid tree, read across levels.

+0
4

0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 1, 1, 4, 4, 3, 3, 5, 5, 2, 2, 5, 5, 3, 3, 4, 4, 1, 1, 5, 5, 4, 4, 7, 7, 3, 3, 8, 8, 5, 5, 7, 7, 2, 2, 7, 7, 5, 5, 8, 8, 3, 3, 7, 7, 4, 4, 5, 5, 1, 1, 6, 6, 5, 5, 9, 9, 4, 4, 11, 11, 7, 7, 10, 10, 3, 3, 11, 11, 8, 8

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

Set N(x) = 1 + floor(x) - frac(x) and let '"' denote the ditto operator, referring to the previously computed expression. Assume the first expression is '0'. Then [0, repeat(N("))] will generate the natural numbers 0, 1, 2, 3, ... and [0, repeat(1/N("))] will generate the rational numbers 0/1, 1/1, 1/2, 2/1, 1/3, 3/2, ... Every reduced nonnegative rational number r appears exactly once in this list as a relatively prime pair [n, d] = r = n/d. We list numerator and denominator one after the other in the sequence.

The apt name 'Euclid tree' is taken from the exposition of Malter, Schleicher and Don Zagier. It is sometimes called the Calkin-Wilf tree. The enumeration is based on Stern's diatomic series (which is a subsequence) and computed by a modification of Dijkstra's 'fusc' function.

The tree listed has root 0, the variant with root 1 is more widely used. Seen as sequences the difference between the two trees is trivial: it is enough to leave out the first two terms; but as trees they are markedly different (see the example section).

REFERENCES

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 3rd ed., 2004.

LINKS

Peter Luschny, Table of n, row(n) for n = 1..12

N. Calkin and H. S. Wilf, Recounting the rationals, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.

Edsger Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. EWD 578: More about the function 'fusc'.

Peter Luschny, Rational Trees and Binary Partitions.

A. Malter, D. Schleicher, and D. Zagier, New looks at old number theory, Amer. Math. Monthly, 120(3), 2013, pp. 243-264.

Moritz A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193-220.

Index entries for sequences related to enumerating the rationals

Index entries for sequences related to trees

FORMULA

Some characteristics in comparison to the tree with root 1, seen as a table with T(n,k) for n >= 1 and 1 <= k <= 2^(n-1). Here Tr(n,k), Tp(n,k), Tq(n,k) denotes the fraction r, the numerator of r and the denominator of r in row n and column k respectively.

With root 0: With root 1:

Root Tr(1,1) 0/1 1/1

Tp(n,1) 0,1,2,3,... 1,1,1,1,...

Tp(n,2^(n-1)) 0,1,2,3,... 1,2,3,4,...

Tq(n,1) 1,1,1,1,... 1,2,3,4,...

Tq(n,2^(n-1)) 1,2,3,4,... 1,1,1,1,...

Sum_k Tp(n,k) 0,2,8,26,... A024023 1,3,9,27,... A000244

Sum_k Tq(n,k) 1,3,9,27,... A000244 1,3,9,27,... A000244

Sum_k 2Tr(n,k) 0,3,9,21,... A068156 2,5,11,23,... A083329

Sum_k Tp(n,k)Tq(n,k) 0,3,17,81,... A052913-1 1,4,18,82,... A052913

----

a(n) = A002487(floor(n/2)). - Georg Fischer, Nov 29 2022

EXAMPLE

The tree with root 0 starts:

[0/1]

[1/1, 1/2]

[2/1, 1/3, 3/2, 2/3]

[3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4]

[4/1, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5]

The tree with root 1 starts:

[1/1]

[1/2, 2/1]

[1/3, 3/2, 2/3, 3/1]

[1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1]

[1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5, 5/1]

MAPLE

# First implementation: use it only if you are not afraid of infinite loops.

a := x -> 1/(1+floor(x)-frac(x)): 0; do a(%) od;

# Second implementation:

lusc := proc(m) local a, b, n; a := 0; b := 1; n := m; while n > 0 do

if n mod 2 = 1 then b := a + b else a := a + b fi; n := iquo(n, 2) od; a end:

R := n -> 3*2^(n-1)-1 .. 2^n: # The range of level n.

EuclidTree_rat := n -> [seq(lusc(k+1)/lusc(k), k=R(n), -1)]:

EuclidTree_num := n -> [seq(lusc(k+1), k=R(n), -1)]:

EuclidTree_den := n -> [seq(lusc(k), k=R(n), -1)]:

EuclidTree_pair := n -> ListTools:-Flatten([seq([lusc(k+1), lusc(k)], k=R(n), -1)]):

seq(print(EuclidTree_pair(n)), n=1..5);

PROG

(Sage)

def A295515(n):

if n == 1: return 0

M = [0, 1]

for b in (n//2 - 1).bits():

M[b] = M[0] + M[1]

return M[1]

print([A295515(n) for n in (1..85)])

CROSSREFS

Cf. A002487, A174981, A294446 (Stern-Brocot tree), A294442 (Kepler's tree), A295511 (Schinzel-Sierpiński tree), A295512 (encoded by semiprimes).

KEYWORD

nonn

AUTHOR

Peter Luschny, Nov 25 2017

STATUS

approved

A295510

The numerators of the fractions in the Schinzel-Sierpiński tree A295511, read across levels. Also an encoding of Stern's diatomic series A002487.

+0
3

2, 2, 3, 3, 7, 5, 7, 2, 17, 7, 11, 5, 11, 13, 5, 3, 241, 17, 29, 7, 17, 31, 43, 13, 43, 11, 17, 13, 29, 193, 11, 2, 13, 11, 37, 73, 67, 29, 41, 7, 23, 97, 79, 31, 73, 29, 19, 5, 37, 43, 73, 31, 157, 17, 23, 13, 41, 43, 199, 17, 19, 11, 7

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

LINKS

Table of n, a(n) for n=1..63.

EXAMPLE

The triangle (row lengths are 2^(n-1)) starts:

1: 2

2: 2, 3

3: 3, 7, 5, 7

4: 2, 17, 7, 11, 5, 11, 13, 5

5: 3, 241, 17, 29, 7, 17, 31, 43, 13, 43, 11, 17, 13, 29, 193, 11

PROG

(Sage) # uses[SSETree from A295511]

def A295510_row(n):

if n == 1: return [2]

return [r.numerator() for r in SSETree(n)]

for n in (1..6): print(A295510_row(n))

CROSSREFS

Cf. A002487, A295510, A295512.

KEYWORD

nonn,tabf

AUTHOR

Peter Luschny, Nov 23 2017

STATUS

approved

A295509

Maxima of the numerators (and also of the denominators) of row n in the Schinzel-Sierpinski tree of fractions A295511.

+0
1

2, 3, 7, 17, 241, 199, 647, 1117, 4231, 8161, 15361, 28057, 67801, 308509, 263101, 515089, 1525921, 2103817, 3376459

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

LINKS

Table of n, a(n) for n=1..19.

PROG

(Sage)

def A295509(n):

return max(A295510_row(n))

[A295509(n) for n in (1..10)]

CROSSREFS

Cf. A295510, A295511, A295512.

KEYWORD

nonn,more

AUTHOR

Peter Luschny, Nov 24 2017

STATUS

approved

page 1

Search completed in 0.007 seconds