login
The Euclid tree, read across levels.
4

%I #60 Nov 29 2022 11:54:30

%S 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,

%T 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,

%U 5,9,9,4,4,11,11,7,7,10,10,3,3,11,11,8,8

%N The Euclid tree, read across levels.

%C 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.

%C 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.

%C 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).

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

%H Peter Luschny, <a href="/A295515/b295515.txt">Table of n, row(n) for n = 1..12</a>

%H N. Calkin and H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/website/recounting.pdf">Recounting the rationals</a>, Amer. Math. Monthly, 107 (No. 4, 2000), pp. 360-363.

%H Edsger Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232. <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF">EWD 578: More about the function 'fusc'.</a>

%H Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/SternsDiatomic">Rational Trees and Binary Partitions</a>.

%H A. Malter, D. Schleicher, and D. Zagier, <a href="http://people.mpim-bonn.mpg.de/zagier/files/doi/10.4169/amer.math.monthly.120.03.243/NewLooksAtOldNumberTheory.pdf">New looks at old number theory</a>, Amer. Math. Monthly, 120(3), 2013, pp. 243-264.

%H Moritz A. Stern, <a href="http://www.digizeitschriften.de/resolveppn/GDZPPN002150301">Über eine zahlentheoretische Funktion</a>, J. Reine Angew. Math., 55 (1858), 193-220.

%H <a href="/index/Ra#rational">Index entries for sequences related to enumerating the rationals</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F 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.

%F With root 0: With root 1:

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

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

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

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

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

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

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

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

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

%F ----

%F a(n) = A002487(floor(n/2)). - _Georg Fischer_, Nov 29 2022

%e The tree with root 0 starts:

%e [0/1]

%e [1/1, 1/2]

%e [2/1, 1/3, 3/2, 2/3]

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

%e [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]

%e .

%e The tree with root 1 starts:

%e [1/1]

%e [1/2, 2/1]

%e [1/3, 3/2, 2/3, 3/1]

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

%e [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]

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

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

%p # Second implementation:

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

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

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

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

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

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

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

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

%o (Sage)

%o def A295515(n):

%o if n == 1: return 0

%o M = [0, 1]

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

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

%o return M[1]

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

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

%K nonn

%O 1,6

%A _Peter Luschny_, Nov 25 2017