A093873 Numerators in Kepler's tree of harmonic fractions.

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, 5, 4, 5, 3, 7, 4, 7, 2, 7, 5, 7, 3, 8, 5, 8, 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, 6

Offset

1,5

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

Links

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

Johannes Kepler, Harmonices Mundi, Liber III, see p. 27.

Index entries for fraction trees

Formula

a(n) = a([n/2])*(1 - n mod 2) + A093875([n/2])*(n mod 2).

a(A029744(n-1)) = 1; a(A070875(n-1)) = 2; a(A123760(n-1)) = 3. - Reinhard Zumkeller, Oct 13 2006

A011782(k) = SUM(a(n)/A093875(n): 2^k<=n<2^(k+1)), k>=0. [Reinhard Zumkeller, Oct 17 2010]

a(1) = 1. For all n>0 a(2n) = a(n), a(2n+1) = A093875(n). - Yosu Yurramendi, Jan 09 2016

a(4n+3) = a(4n+1), a(4n+2) = a(4n+1) - a(4n), a(4n+1) = A071585(n). - Yosu Yurramendi, Jan 11 2016

G.f. G(x) satisfies G(x) = x + (1+x) G(x^2) + Sum_{k>=2} x (1+x^(2^(k-1))) G(x^(2^k)). - Robert Israel, Jan 11 2016

a(2^(m+1)+k) = a(2^(m+1)+2^m+k) = A020651(2^m+k), m>=0, 0<=k<2^m. - Yosu Yurramendi, May 18 2016

a(k) = A020651(2^(m+1)+k) - A020651(2^m+k), m>0, 0<k<2^m. - Yosu Yurramendi, Jun 01 2016

a(2^(m+1)+k) - a(2^m+k) = a(k) , m >=0, 0 <= k < 2^m. For k=0 a(0)=0 is needed. - Yosu Yurramendi, Jul 22 2016

a(2^(m+2)-1-k) = a(2^(m+1)-1-k) + a(2^m-1-k), m >= 1, 0 <= k < 2^m. - Yosu Yurramendi, Jul 22 2016

a(2^m-1-(2^r -1)) = A000045(m-r), m >= 1, 0 <= r <= m-1. - Yosu Yurramendi, Jul 22 2016

a(2^m+2^r) = m-r, , m >= 1, 0 <= r <= m-1 ; a(2^m+2^r+2^(r-1)) = m-(r-1), m >= 2, 0 <= r <= m-1. - Yosu Yurramendi, Jul 22 2016

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

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

Maple

M:= 8: # to get a(1) .. a(2^M-1)
gen[1]:= [1];
for n from 2 to M do
  gen[n]:= map(t -> (numer(t)/(numer(t)+denom(t)),
      denom(t)/(numer(t)+denom(t))), gen[n-1]);
od:
seq(op(map(numer, gen[i])), i=1..M): # Robert Israel, Jan 11 2016

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]; A093873 = Table[num[n], {n, 1, 97}] (* Jean-François Alcover, Dec 16 2011 *)

Prog

(Haskell)
{-# LANGUAGE ViewPatterns #-}
import Data.Ratio((%), numerator, denominator)
rat :: Rational -> (Integer, Integer)
rat r = (numerator r, denominator r)
data Harmony = Harmony Harmony Rational Harmony
rows :: Harmony -> [[Rational]]
rows (Harmony hL r hR) = [r] : zipWith (++) (rows hL) (rows hR)
kepler :: Rational -> Harmony
kepler r = Harmony (kepler (i%(i+j))) r (kepler (j%(i+j)))
.......... where (rat -> (i, j)) = r
-- Full tree of Kepler's harmonic fractions:
k = rows $ kepler 1 :: [[Rational]] -- as list of lists
h = concat k :: [Rational] -- flattened
a093873 n = numerator $ h !! (n - 1)
a093875 n = denominator $ h !! (n - 1)
a011782 n = numerator $ (map sum k) !! n -- denominator == 1
-- length (k !! n) == 2^n
-- numerator $ (map last k) !! n == fibonacci (n + 1)
-- denominator $ (map last k) !! n == fibonacci (n + 2)
-- numerator $ (map maximum k) !! n == n
-- denominator $ (map maximum k) !! n == n + 1
-- eop.
-- Reinhard Zumkeller, Oct 17 2010

Crossrefs

The denominators are in A093875. 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.

See A294442 for another version of Kepler's tree of fractions.

Sequence in context: A280363 A217743 A238845 * A353371 A353334 A353304

Adjacent sequences: A093870 A093871 A093872 * A093874 A093875 A093876

Keyword

nonn,easy,frac,look,hear

Author

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

Status

approved