A093875 Denominators in Kepler's tree of harmonic fractions.

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

Offset

1,2

Comments

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

It appears that A071585 is a bisection of this sequence, which itself is a bisection of A093873. - Yosu Yurramendi, Jan 09 2016

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Index entries for fraction trees

Formula

a(n) = a([n/2]) + A093873([n/2]).

Conjecture of the comment in detail: a(2n+1) = a(2n), n > 0; a(2n+1) = A071585(n), n >= 0; a(2n) = A071585(n), n > 0. - Yosu Yurramendi, Jun 22 2016

a(2n) - A093873(2n) = a(n), n > 0; a(2n+1) - A093873(2n+1) = A093873(n), n > 0. - Yosu Yurramendi, Jul 23 2016

From Yosu Yurramendi, Jul 25 2016: (Start)

a(2^m) = m+1, m >= 0; a(2^m + 2) = 2m - 1, m >= 1; a(2^m - 1) = A000045(m+2), m >= 1.

a(2^(m+1) + k) - a(2^m + k) = a(k), m > 0, 0 <= k < 2^m. For k=0, a(0) = 1 is needed.

a(2^(m+2) - k - 1) = a(2^(m+1) - k - 1) + a(2^m - k - 1), m >= 0, 0 <= k < 2^m. (End)

Example

The first few fractions are:
1 1 1 1 2 1 2 1 3 2 3 1 3 2 3 1 4 3 4 2 5 3 5 1 4 3 4 2 5 3 5
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ...
1 2 2 3 3 3 3 4 4 5 5 4 4 5 5 5 5 7 7 7 7 8 8 5 5 7 7 7 7 8 8

Mathematica

num[1] = num[2] = 1; den[1] = 1; den[2] = 2; num[n_?EvenQ] := num[n] = num[n/2]; den[n_?EvenQ] := den[n] = num[n/2] + den[n/2]; num[n_?OddQ] := num[n] = den[(n-1)/2]; den[n_?OddQ] := den[n] = num[(n-1)/2] + den[(n-1)/2]; A093875 = Table[den[n], {n, 1, 83}] (* Jean-François Alcover, Dec 16 2011 *)

Prog

(PARI) a(n) = if(n==1, 1, my(n=n\2, x=1, y=1); for(i=0, logint(n, 2), if(bittest(n, i), [x, y]=[x+y, x], [x, y]=[x, x+y])); x) \\ Mikhail Kurkov, Mar 11 2023

Crossrefs

The numerators are in A093873. Usually one only considers the left-hand half of the tree, which gives the fractions A020651/A086592. See A086592 for more information, references to Kepler, etc.

Cf. A071585, A093873

Sequence in context: A116458 A354166 A331854 * A329242 A266193 A114214

Adjacent sequences: A093872 A093873 A093874 * A093876 A093877 A093878

Keyword

nonn,easy,frac

Author

N. J. A. Sloane and Reinhard Zumkeller, May 24 2004

Status

approved