

A020651


Denominators in recursive bijection from positive integers to positive rationals (the bijection is f(1) = 1, f(2n) = f(n)+1, f(2n+1) = 1/(f(n)+1)).


21



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

If we insert an initial 1, this is the sequence of numerators in lefthand 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 (leftaligned 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 mth 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)1k)  a(2^m1k) = A093873(k), m = 0,1,2,..., k = 0,1,2,...,2^m1).
If the rows are written in a rightaligned 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


LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000
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 (illustrates the A020651/A086592tree).
Index entries for fraction trees


FORMULA

a(1) = 1, a(2n) = a(n), a(2n+1) = A020650(2n).  Antti Karttunen, May 26 2004
a(2n) = A020650(2n+1).  Yosu Yurramendi, Jul 17 2014
a(2^m + k) = A093873(2^(m+1) + k) = A093873(2^(m+1) + 2^m + k), m >= 0, 0 <= k < 2^m.  Yosu Yurramendi, May 18 2016
a(2^m + 2^r + k) = A093873(2^r + k)*(m(r1)) + A093873(k), m >= 0, r <= m1, 0 <= k < 2^r. For k=0 A093873(0) = 0 is needed.  Yosu Yurramendi, Jul 30 2016
a((2n+1)*2^m) = A086592(n), m >= 0, n > 0. For n = 0 A086592(0) = 1 is needed.  Yosu Yurramendi, Feb 14 2017
a(4n+2) = a(4n+1)  a(4n) = a(2n+1) = a(4n+1)  a(n), n > 0.  Yosu Yurramendi, May 08 2018
a(1) = 1, a(n+1) = 2*floor(1/a(n))+11/a(n).  Jan Malý, Jul 30 2019


EXAMPLE

1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, 1/4, 4/3, ...


MAPLE

A020651 := n > `if`((n < 2), n, `if`(type(n, even), A020651(n/2), A020650(n1)));


MATHEMATICA

f[1] = 1; f[n_?EvenQ] := f[n] = f[n/2]+1; f[n_?OddQ] := f[n] = 1/(f[(n1)/2]+1); a[n_] := Denominator[f[n]]; Table[a[n], {n, 1, 94}] (* JeanFrançois Alcover, Nov 22 2011 *)


PROG

(Haskell)
import Data.List (transpose); import Data.Ratio (denominator)
a020651_list = map denominator ks where
ks = 1 : concat (transpose [map (+ 1) ks, map (recip . (+ 1)) ks])
 Reinhard Zumkeller, Feb 22 2014
(R)
N < 25 # arbitrary
a < c(1, 1, 2)
for(n in 1:N){
a[4*n] < a[2*n]
a[4*n+1] < a[2*n] + a[2*n+1]
a[4*n+2] < a[2*n+1]
a[4*n+3] < a[2*n] + a[2*n+1]
}
a
# Yosu Yurramendi, Jul 13 2014


CROSSREFS

See A294442 and A093873/A093875 for two different versions of the Kepler tree.
Cf. A020650, A086592, A093873.
Sequence in context: A038568 A071912 A070940 * A294442 A281392 A287051
Adjacent sequences: A020648 A020649 A020650 * A020652 A020653 A020654


KEYWORD

nonn,easy,frac,nice


AUTHOR

David W. Wilson


EXTENSIONS

Entry revised by N. J. A. Sloane, May 24 2004


STATUS

approved



