cp's OEIS Frontend

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

%I A020651 #128 Dec 26 2024 10:15:41
%S A020651 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,
%T A020651 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,
%U A020651 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
%N 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)).
%C A020651 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.
%C A020651 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
%C A020651 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
%C A020651 From _Yosu Yurramendi_, Jul 13 2014: (Start)
%C A020651 If the terms (n > 0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
%C A020651    1,
%C A020651    1,2,
%C A020651    1,3,2,3,
%C A020651    1,4,3,4,2,5,3,5,
%C A020651    1,5,4,5,3,7,4,7,2, 7,5, 7,3, 8,5, 8,
%C A020651    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,
%C A020651 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).
%C A020651 If the rows are written in a right-aligned fashion:
%C A020651                                                                           1,
%C A020651                                                                        1, 2,
%C A020651                                                                   1, 3,2, 3,
%C A020651                                                         1, 4,3, 4,2, 5,3, 5,
%C A020651                                       1,5,4,5,3, 7,4, 7,2, 7,5, 7,3, 8,5, 8,
%C A020651   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,
%C A020651 then each column k is a Fibonacci sequence. (End)
%C A020651 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
%H A020651 T. D. Noe, <a href="/A020651/b020651.txt">Table of n, a(n) for n = 1..10000</a>
%H A020651 D. N. Andreev, <a href="http://www.mathnet.ru/eng/mp12">On a Wonderful Numbering of Positive Rational Numbers</a>, Matematicheskoe Prosveshchenie, Series 3, volume 1, 1997, pages 126-134 (in Russian).  a(n) = denominator of r(n).
%H A020651 Godofredo Iommi and Mario Ponce, <a href="https://arxiv.org/abs/2404.03768">Odometers in non-compact spaces</a>, arXiv:2404.03768 [math.DS], 2024. See p. 19.
%H A020651 Johannes Kepler, <a href="http://web.archive.org/web/20081009062459/http://ndirty.cute.fi/~karttu/Kepler/a086592.htm">Excerpt from the Chapter II of the Book III of the Harmony of the World: On the seven harmonic divisions of the string</a> (illustrates the A020651/A086592-tree).
%H A020651 Pelegrí Viader, Jaume Paradís and Lluís Bibiloni, <a href="https://doi.org/10.1006/jnth.1998.2294">A New Light on Minkowski's ?(x) Function</a>, J. Number Theory, 73 (2) (1998), 212-227. See p. 215.
%H A020651 Shen Yu-Ting, <a href="https://doi.org/10.2307/2320374">A Natural Enumeration of Non-Negative Rational Numbers -- An Informal Discussion</a>, American Mathematical Monthly, volume 87, number 1, January 1980, pages 25-29.  a(n) = denominator of gamma_n.
%H A020651 <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%H A020651 <a href="/index/Mu#music">Index entries for sequences related to music</a>
%F A020651 a(1) = 1, a(2n) = a(n), a(2n+1) = A020650(2n). - _Antti Karttunen_, May 26 2004
%F A020651 a(2n) = A020650(2n+1). - _Yosu Yurramendi_, Jul 17 2014
%F A020651 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
%F A020651 a(2^m + 2^r + k) = A093873(2^r + k)*(m-(r-1)) + A093873(k), m >= 0, r <= m-1, 0 <= k < 2^r. For k=0 A093873(0) = 0 is needed. - _Yosu Yurramendi_, Jul 30 2016
%F A020651 a((2n+1)*2^m) = A086592(n), m >= 0, n > 0. For n = 0 A086592(0) = 1 is needed. - _Yosu Yurramendi_, Feb 14 2017
%F A020651 a(4n+2) = a(4n+1) - a(4n) = a(2n+1) = a(4n+1) - a(n), n > 0. - _Yosu Yurramendi_, May 08 2018
%F A020651 a(1) = 1, a(n+1) = 2*floor(1/a(n))+1-1/a(n). - _Jan Malý_, Jul 30 2019
%F A020651 a(n) = A002487(A231551(n)), n > 0. - _Yosu Yurramendi_, Jul 15 2021
%e A020651 1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, 1/4, 4/3, ...
%p A020651 A020651 := n -> `if`((n < 2),n,`if`(type(n,even), A020651(n/2), A020650(n-1)));
%t A020651 f[1] = 1; f[n_?EvenQ] := f[n] = f[n/2]+1; f[n_?OddQ] := f[n] = 1/(f[(n-1)/2]+1); a[n_] := Denominator[f[n]]; Table[a[n], {n, 1, 94}] (* _Jean-François Alcover_, Nov 22 2011 *)
%o A020651 (Haskell)
%o A020651 import Data.List (transpose); import Data.Ratio (denominator)
%o A020651 a020651_list = map denominator ks where
%o A020651    ks = 1 : concat (transpose [map (+ 1) ks, map (recip . (+ 1)) ks])
%o A020651 -- _Reinhard Zumkeller_, Feb 22 2014
%o A020651 (R)
%o A020651 N <- 25 # arbitrary
%o A020651 a <- c(1,1,2)
%o A020651 for(n in 1:N){
%o A020651   a[4*n]   <- a[2*n]
%o A020651   a[4*n+1] <- a[2*n] + a[2*n+1]
%o A020651   a[4*n+2] <-          a[2*n+1]
%o A020651   a[4*n+3] <- a[2*n] + a[2*n+1]
%o A020651 }
%o A020651 a
%o A020651 # _Yosu Yurramendi_, Jul 13 2014
%Y A020651 See A294442 and A093873/A093875 for two different versions of the Kepler tree.
%Y A020651 Cf. A020650, A086592.
%K A020651 nonn,easy,frac,nice
%O A020651 1,3
%A A020651 _David W. Wilson_
%E A020651 Entry revised by _N. J. A. Sloane_, May 24 2004