cp's OEIS Frontend

It would be nice to have a formula or recurrence.

If we insert an initial 1, this is the sequence of numerators in left-hand half of Kepler's tree of fractions. Form a tree of fractions by beginning with 1/1 and then giving every node i/j two descendants labeled i/(i+j) and j/(i+j). See A086592 for denominators. See A294442 for the Kepler tree itself.

Level n of the tree consists of 2^n nodes: 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; ... Fibonacci numbers occur at the right edge this tree, i.e., a(A000225(n)) = A000045(n+1). The fractions are given in their reduced form, thus gcd(A020650(n), A020651(n)) = 1 and gcd(A020651(n), A086592(n)) = 1 for all n. - Antti Karttunen, May 26 2004

A generalization which includes the "rabbit tree" (A226080) and "all rationals tree" (A226130) follows. Suppose that a,b,c,d,e,f,g,h are complex numbers. Let S be the set of numbers defined by these rules: (1) 1 is in S; (2) if x is in S and cx+d is not 0, then U(x) = (ax+b)/(cx+d) is in S; (3) if x is in S and gx+h is not 0, then D(x) = (ex+f)/(gx+h) is in S. If an infinite path in the resulting tree has convergent nodes, then there is some node after which the path is "updown zigzag" ((UoD)o(UoD)o ...) or "downup zigzag" (DoU)o(DoU)o ...). If ag+ch is not 0, then the updown zigzag limit is invariant of x and equals [ae + cf - bg - dh + sqrt(X)]/(2(ag + ch)), where X = (ae + cf - bg - dh)^2 + 4(be + df + ag + ch). If ce + dg is not 0, then the downup zigzag limit is invariant of x and equals [ae + bg - cf - dh + sqrt(Y)]/(2(ce + dg)), where Y = (ae + bg - cf - dh)^2 + 4(af + bh)(ce + dg)) = X. Thus, for the tree A020651, the updown zigzag limit is -1 + sqrt(2) and the downup zigzag limit, sqrt(2). - Clark Kimberling, Nov 10 2013

From Yosu Yurramendi, Jul 13 2014: (Start)

If the terms (n > 0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...

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,

then the sum of the m-th row is 3^m (m = 0,1,2,), and each column is an arithmetic sequence. The differences of the arithmetic sequences, except the first on the left, give the sequence A093873 (Numerators in Kepler's tree of harmonic fractions) (a(2^(m+1)-1-k) - a(2^m-1-k) = A093873(k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).

If the rows are written in a right-aligned fashion:

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,

then each column k is a Fibonacci sequence. (End)

For m >= 0, a(2^m) = 1 and a(3*2^m) = 2. For n >= 0, a(A070875(n)) = 3 (for m >= 0, a(5*2^m) = 3 and a(7*2^m) = 3). - Yosu Yurramendi, Jun 02 2016

Form a tree of fractions by beginning with 1/1 and then giving every node i/j two descendants labeled i/(i+j) and j/(i+j).

Equivalently, a(n) is the number of distinct terms in row n of the Stern-Brocot sequence (A002487) when that sequence is divided into blocks of lengths 1, 2, 4, 8, 16, 32, ...

It would be nice to have a formula or recurrence, or even some bounds. Empirically, a(n) seems to be roughly 2^(2n/3) for the known values. Note that the first half of row n has about 2^(n-2) terms, and the maximal multiplicity is given by A293957(n), so 2^(n-2)/A293957(n) is a lower bound on a(n), which seems not too bad for the known values. - N. J. A. Sloane, Nov 04 2017

The multiset of terms in row n of Stern's diatomic array, with unique elements counted by a(n), is the same as the multiset of numerators of fractions in row n of Kepler's tree. Indeed, a fraction p/q is in row n-1 of Kepler's tree if and only if p/q and q/p are in row n of Calkin-Wilf tree. To form row n of Stern's diatomic array, one should take either numerators and denominators of fractions less than 1 or all numerators from Calkin-Wilf tree row n, in either case p/q and q/p contribute p and q. In Kepler's tree, a fraction p/q contributes p and q as numerators to the next row, i.e. row n. See A294442 for Kepler's tree and A294444 for the number of distinct denominators in it. - Andrey Zabolotskiy, Dec 05 2024

Schroeder, p. 281 states "The ordering with which the iterates x_n fall into the 2^m different chaos bands [order as to magnitude] is also the same as the ordering of the iterates in a stable orbit of period length P = 2^m. For example, for both the period-4 orbit and the four chaos bands, the iterates, starting with the largest iterate x_1, are ordered as follows: x_1 > x_3 > x_4 > x_2."

From Andrey Zabolotskiy, Dec 06 2024: (Start)

For n>0, row n-1 is the permutation relating row n of the left half of Stern-Brocot tree with row n of Kepler's tree of fractions. Specifically, if K_n(k) [resp. SB_n(k)] is the k-th fraction in the n-th row of A294442 [resp. A057432], where 1/2 is in row 1 and k=1..2^(n-1), then SB_n(k) = K_n(T(n-1, k)).

The inverse permutation is row n of A131271.

Equals A362160+1. (End)

Also denominator of alternate fractions in Kepler's tree as shown in A294442. - N. J. A. Sloane, Nov 20 2017

In a knockout competition with 2^n players, arranging the competition brackets (see Wikipedia) in T(n,k) order, where T(n,k) is the rank of the k-th player, ensures that highest ranked players cannot meet until the later stages of the competition. None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition. At the same time the top ranked players in each match meet the lowest ranked player possible consistent with this rule. The sequence for the top ranked players meeting the highest ranked player possible is A049773. - Colin Hall, Feb 28 2012

Ranks in natural order of 2^n increasing real numbers appearing in limit cycles of interval iterations, or Median Spiral Order. [See the works by Demongeot & Waku]

From Andrey Zabolotskiy, Dec 06 2024 (Start):

For n>0, row n-1 is the permutation relating row n of Kepler's tree of fractions with row n of the left half of Stern-Brocot tree. Specifically, if K_n(k) [resp. SB_n(k)] is the k-th fraction in the n-th row of A294442 [resp. A057432], where 1/2 is in row 1 and k=1..2^(n-1), then K_n(k) = SB_n(T(n-1, k)).

The inverse permutation is row n of A088208.

When 1 is subtracted from each term, rows 3-5 become A240908, A240909, A240910. (End)

A conjecture of Schinzel and Sierpiński asserts that every positive rational number r can be represented as a quotient of shifted primes such that r = (p-1)/(q-1).

The function r -> [p, q] will be called the Schinzel-Sierpiński encoding of r if q is the smallest prime such that r = (p-1)/(q-1) for some prime p. In the case that no pair of such primes exists we set by convention p = q = 1.

The Schinzel-Sierpiński tree of fractions is the Euclid tree A295515 with root 1 and fractions represented by the Schinzel-Sierpiński encoding.

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.

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