login
A295512
The Euclid tree with root 1 encoded by semiprimes, read across levels.
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
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
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.
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:
4
-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
KEYWORD
sign,tabf
AUTHOR
Peter Luschny, Nov 23 2017
STATUS
approved