A294446 -id:A294446 - cp's OEIS frontend

A294442 Kepler's tree of fractions, read across rows (the fraction i/j is represented as the pair i,j).

1, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 4, 2, 5, 3, 5, 1, 5, 4, 5, 3, 7, 4, 7, 2, 7, 5, 7, 3, 8, 5, 8, 1, 6, 5, 6, 4, 9, 5, 9, 3, 10, 7, 10, 4, 11, 7, 11, 2, 9, 7, 9, 5, 12, 7, 12, 3, 11, 8, 11, 5, 13, 8, 13, 1, 7, 6, 7, 5, 11, 6, 11, 4, 13, 9, 13, 5, 14, 9, 14, 3, 13, 10, 13, 7, 17, 10, 17, 4, 15, 11, 15, 7, 18, 11

Offset: 0

N. J. A. Sloane, Nov 20 2017

The first row contains the single fraction 1/1,
the second row contains the single fraction 1/2,
and thereafter below each fraction i/j we write two fractions i/(i+j), j/(i+j).
If we just look at the numerators we recover the same sequence, and if we just look at the denominators we get A086593 with the terms (after the first) repeated.
Sequence A020651 is almost the same as this, except that it lacks one of the initial 1's, and the definition focuses on single numbers rather than pairs of numbers or fractions. For that reason it seems to be best to have a separate entry (this sequence) for the actual tree.

			The tree begins as follows:
..............1/1
...............|
..............1/2
.........../.......\
......1/3.............2/3
...../....\........../...\
..1/4.....3/4.....2/5.....3/5
../..\..../..\..../..\..../..\
1/5.4/5.3/7.4/7.2/7.5/7.3/8.5/8

Michael De Vlieger, Table of n, a(n) for n = 0..16383
Johannes Kepler, Excerpt from the Chapter II of the Book III of the Harmony of the World: On the seven harmonic divisions of the string.
Richard J. Mathar, The Kepler binary tree of reduced fractions, 2017.
Index entries for fraction trees.
Index entries for sequences related to music.

Cf. A020651, A086593.
A different version of the Kepler tree is described in A093873.
See A294446 for the tree of Farey fractions.

# S[n] is the list of fractions, written as pairs [i,j], in row n of Kepler's triangle
S[0]:=[[1,1]]; S[1]:=[[1,2]];
for n from 2 to 10 do
S[n]:=[];
for k from 1 to nops(S[n-1]) do
t1:=S[n-1][k];
a:=[t1[1],t1[1]+t1[2]];
b:=[t1[2],t1[1]+t1[2]];
S[n]:=[op(S[n]),a,b];
od:
lprint(S[n]);
od:

Map[{Numerator@ #, Denominator@ #} &, #] &@ Flatten@ Nest[Append[#, Flatten@ Map[{#1/(#1 + #2), #2/(#1 + #2)} & @@ {Numerator@ #, Denominator@ #} &, Last@ #]] &, {{1/1}, {1/2}}, 5] // Flatten (* Michael De Vlieger, Apr 18 2018 *)

A295515 The Euclid tree, read across levels.

Original entry on oeis.org

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

Offset: 1

Peter Luschny, Nov 25 2017

nonn

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

			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]

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

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

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

# 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);

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)])

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

cp's OEIS Frontend

A294442 Kepler's tree of fractions, read across rows (the fraction i/j is represented as the pair i,j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica