login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A295515 The Euclid tree, read across levels. 3
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, 3nd. ed., 2004

LINKS

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

N. Calkin, 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, 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.

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

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

Sequence in context: A230351 A102481 A231201 * A110659 A308068 A100522

Adjacent sequences:  A295512 A295513 A295514 * A295516 A295517 A295518

KEYWORD

nonn

AUTHOR

Peter Luschny, Nov 25 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 11:44 EDT 2019. Contains 328108 sequences. (Running on oeis4.)