This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A295515 #62 Aug 11 2025 07:14:56
%S A295515 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 A295515 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 A295515 5,9,9,4,4,11,11,7,7,10,10,3,3,11,11,8,8
%N A295515 The Euclid tree, read across levels.
%C A295515 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 A295515 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 A295515 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 A295515 M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 3rd ed., 2004.
%H A295515 Peter Luschny, <a href="/A295515/b295515.txt">Table of n, row(n) for n = 1..12</a>
%H A295515 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 A295515 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 A295515 Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/SternsDiatomic">Rational Trees and Binary Partitions</a>.
%H A295515 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 A295515 Moritz A. Stern, <a href="https://gdz.sub.uni-goettingen.de/id/PPN243919689_0055">Über eine zahlentheoretische Funktion</a>, J. Reine Angew. Math., 55 (1858), 193-220.
%H A295515 <a href="/index/Ra#rational">Index entries for sequences related to enumerating the rationals</a>
%H A295515 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A295515 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 A295515 With root 0: With root 1:
%F A295515 Root Tr(1,1) 0/1 1/1
%F A295515 Tp(n,1) 0,1,2,3,... 1,1,1,1,...
%F A295515 Tp(n,2^(n-1)) 0,1,2,3,... 1,2,3,4,...
%F A295515 Tq(n,1) 1,1,1,1,... 1,2,3,4,...
%F A295515 Tq(n,2^(n-1)) 1,2,3,4,... 1,1,1,1,...
%F A295515 Sum_k Tp(n,k) 0,2,8,26,... A024023 1,3,9,27,... A000244
%F A295515 Sum_k Tq(n,k) 1,3,9,27,... A000244 1,3,9,27,... A000244
%F A295515 Sum_k 2Tr(n,k) 0,3,9,21,... A068156 2,5,11,23,... A083329
%F A295515 Sum_k Tp(n,k)Tq(n,k) 0,3,17,81,... A052913-1 1,4,18,82,... A052913
%F A295515 ----
%F A295515 a(n) = A002487(floor(n/2)). - _Georg Fischer_, Nov 29 2022
%e A295515 The tree with root 0 starts:
%e A295515 [0/1]
%e A295515 [1/1, 1/2]
%e A295515 [2/1, 1/3, 3/2, 2/3]
%e A295515 [3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4]
%e A295515 [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 A295515 .
%e A295515 The tree with root 1 starts:
%e A295515 [1/1]
%e A295515 [1/2, 2/1]
%e A295515 [1/3, 3/2, 2/3, 3/1]
%e A295515 [1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1]
%e A295515 [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 A295515 # First implementation: use it only if you are not afraid of infinite loops.
%p A295515 a := x -> 1/(1+floor(x)-frac(x)): 0; do a(%) od;
%p A295515 # Second implementation:
%p A295515 lusc := proc(m) local a, b, n; a := 0; b := 1; n := m; while n > 0 do
%p A295515 if n mod 2 = 1 then b := a + b else a := a + b fi; n := iquo(n, 2) od; a end:
%p A295515 R := n -> 3*2^(n-1)-1 .. 2^n: # The range of level n.
%p A295515 EuclidTree_rat := n -> [seq(lusc(k+1)/lusc(k), k=R(n), -1)]:
%p A295515 EuclidTree_num := n -> [seq(lusc(k+1), k=R(n), -1)]:
%p A295515 EuclidTree_den := n -> [seq(lusc(k), k=R(n), -1)]:
%p A295515 EuclidTree_pair := n -> ListTools:-Flatten([seq([lusc(k+1), lusc(k)], k=R(n), -1)]):
%p A295515 seq(print(EuclidTree_pair(n)), n=1..5);
%o A295515 (Sage)
%o A295515 def A295515(n):
%o A295515 if n == 1: return 0
%o A295515 M = [0, 1]
%o A295515 for b in (n//2 - 1).bits():
%o A295515 M[b] = M[0] + M[1]
%o A295515 return M[1]
%o A295515 print([A295515(n) for n in (1..85)])
%Y A295515 Cf. A002487, A174981, A294446 (Stern-Brocot tree), A294442 (Kepler's tree), A295511 (Schinzel-Sierpiński tree), A295512 (encoded by semiprimes).
%K A295515 nonn
%O A295515 1,6
%A A295515 _Peter Luschny_, Nov 25 2017