A071585 -id:A071585 - cp's OEIS frontend

A007306 Denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range [0,1]).

1, 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11, 10, 11, 9, 6, 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19, 17, 18, 21, 19, 14, 13, 17, 18, 15, 13, 14, 11, 7, 8, 13, 17, 16, 19, 23, 22, 17, 19, 26, 29, 25, 24

Offset: 0

N. J. A. Sloane

Also number of odd entries in n-th row of triangle of Stirling numbers of the second kind (A008277). - Benoit Cloitre, Feb 28 2004
Apparently (except for the first term) the number of odd entries in the alternated diagonals of Pascal's triangle at 45 degrees slope. - Javier Torres (adaycalledzero(AT)hotmail.com), Jul 26 2009
The Kn3 and Kn4 triangle sums, see A180662 for their definitions, of Sierpiński's triangle A047999 equal a(n+1). - Johannes W. Meijer, Jun 05 2011
From Yosu Yurramendi, Jun 23 2014: (Start)
If the terms (n>1) are written as an array:
  2,
  3,  3,
  4,  5,  5,  4,
  5,  7,  8,  7,  7,  8,  7,  5,
  6,  9, 11, 10, 11, 13, 12,  9,  9, 12, 13, 11, 10, 11,  9,  6,
  7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19,17,18,
then the sum of the k-th row is 2*3^(k-2), each column is an arithmetic progression. The differences of the arithmetic progressions give the sequence itself (a(2^(m+1)+1+k) - a(2^m+1+k) = a(k+1), m >= 1, 1 <= k <= 2^m), because a(n) = A002487(2*n-1) and A002487 has these properties. A071585 also has these properties. Each row is a palindrome: a(2^(m+1)+1-k) = a(2^m+k), m >= 0, 1 <= k <= 2^m.
If the terms (n>0) are written in this way:
  1,
  2, 3,
  3, 4,  5,  5,
  4, 5,  7,  8,  7,  7,  8,  7,
  5, 6,  9, 11, 10, 11, 13, 12,  9,  9, 12, 13, 11, 10, 11,  9,
  6, 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19,
each column is an arithmetic progression and the steps also give the sequence itself (a(2^(m+1)+k) - a(2^m+k) = a(k), m >= 0, 0 <= k < 2^m). Moreover, by removing the first term of each column:
a(2^(m+1)+k) = A049448(2^m+k+1), m >= 0, 0 <= k < 2^m.
(End)
k > 1 occurs in this sequence phi(k) = A000010(k) times. - Franklin T. Adams-Watters, May 25 2015
Except for the initial 1, this is the odd bisection of A002487. The even bisection of A002487 is A002487 itself. - Franklin T. Adams-Watters, May 25 2015
For all m >= 0, max_{k=1..2^m} a(2^m+k) = A000045(m+3) (Fibonacci sequence). - Yosu Yurramendi, Jun 05 2016
For all n >= 2, max(m: a(2^m+k) = n, 1<=k<=2^m) = n-2. - Yosu Yurramendi, Jun 05 2016
a(2^m+1) = m+2, m >= 0; a(2^m+2) = 2m+1, m>=1; min_{m>=0, k=1..2^m} a(2^m+k) = m+2; min_{m>=2, k=2..2^m-1} a(2^m+k) = 2m+1. - Yosu Yurramendi, Jun 06 2016
a(2^(m+2) + 2^(m+1) - k) - a(2^(m+1) + 2^m-k) = 2*a(k+1), m >= 0, 0 <= k <= 2^m. - Yosu Yurramendi, Jun 09 2016
If the initial 1 is omitted, this is the number of nonzero entries in row n of the generalized Pascal triangle P_2, see A282714 [Leroy et al., 2017]. - N. J. A. Sloane, Mar 02 2017
Apparently, this sequence was introduced by Johann Gustav Hermes in 1894. His paper gives a strong connection between this sequence and the so-called "Gaussian brackets" ("Gauss'schen Klammer"). For an independent discussion about Gaussian brackets, see the relevant MathWorld article and the article by Herzberger (1943). Srinivasan (1958) gave another, more modern, explanation of the connection between this sequence and the Gaussian brackets. (Parenthetically, J. G. Hermes is the mathematician who completed or constructed the regular polygon with 65537 sides.) - Petros Hadjicostas, Sep 18 2019

			[ 0/1; 1/1; ] 1/2; 1/3, 2/3; 1/4, 2/5, 3/5, 3/4; 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5; ...

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 61.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, p. 158.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Suayb S. Arslan, Asymptotically MDS Array BP-XOR Codes, arXiv:1709.07949 [cs.IT], 2017.
Alexander Bogomolny, Stern-Brocot tree.
J. Hermes, Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden (The number of partitions of a rational integer, Part I), Mathematischen Annalen 45(3) (1894), 371-380.
J. Hermes, Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden (The number of partitions of a rational integer, Part I), Mathematischen Annalen 45(3) (1894), 371-380.
J. Hermes, Anzahl der Zerlegungen einer ganzen, rationalen Zahl in Summanden, II (The number of partitions of a rational integer, Part II), Mathematischen Annalen 47(2-3) (1896), 281-297.
M. Herzberger, Gaussian optics and Gaussian brackets, Journal of the Optical Society of America 33(12) (1943), 651-655. [This paper gives a clear description of Gaussian brackets that are related to this sequence as explained by Hermes (1894).]
Jennifer Lansing, On the Stern sequence and a related sequence, Ph.D. dissertation in Mathematics, University of Illinois at Urbana-Champaign, 2014. [This doctoral dissertation discusses the so-called Stern sequence on which Hermes' papers are based (according to Srinivasan (1958)).]
Julien Leroy, Michel Rigo, and Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics 340 (2017), 862-881.
Julien Leroy, Michel Rigo, and Manon Stipulanti, Counting subword occurrences in base-b expansions, Integers (2018) 18A, Article #A13.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math. 210 (2000), 137-149.
N. J. A. Sloane, Stern-Brocot or Farey Tree.
M. S. Srinivasan, The enumeration of positive rational numbers, Proc. Indian Acad. Sci. Sect. A 47 (1958), 12-24.
M. Stern, Über eine zahlentheoretische Function, Journal für die reine und angewandte Mathematik 55 (1858), 193-220. [According to Srinivasan (1958), Hermes's (1894) paper, where this sequence is introduced, is based on Stern's sequence.]
Manon Stipulanti, Convergence of Pascal-Like Triangles in Parry-Bertrand Numeration Systems, arXiv:1801.03287 [math.CO], 2018.
Javier Torres Suarez, Number theory - geometric connection (part 2) (YouTube video that mentions this sequence - link sent by Pacha Nambi, Aug 26 2009).
Eric Weisstein's World of Mathematics, Gaussian brackets; they are related to this sequence.
Wikipedia, Johann Gustav Hermes. [He is the person who introduced this sequence and the person who completed or constructed a regular polygon with 65537 sides.]
Index entries for fraction trees
Index entries for sequences related to Stern's sequences

For numerators see A007305.
Cf. A001222, A002487, A006842, A006843, A047679, A054424, A065674-A065675, A065810, A260443, A277324, A277328, A283986, A283987, A283988, A284009, A284265, A284266, A284267, A284268, A284565, A284566, A285106, A285107, A285108, A287731, A287732.
See also A282714.

[1] cat [&+[Binomial(n+k,2*k) mod 2: k in [0..n]]: n in [0..80]]; // Vincenzo Librandi, Jun 10 2019

A007306 := proc(n): if n=0 then 1 else A002487(2*n-1) fi: end: A002487 := proc(m) option remember: local a, b, n; a := 1; b := 0; n := m; while n>0 do if type(n, odd) then b := a + b else a := a + b end if; n := floor(n/2); end do; b; end proc: seq(A007306(n),n=0..77); # Johannes W. Meijer, Jun 05 2011

a[0] = 1; a[n_] := Sum[ Mod[ Binomial[n+k-1, 2k] , 2], {k, 0, n}]; Table[a[n], {n, 0, 77}] (* Jean-François Alcover, Dec 16 2011, after Paul Barry *)
a[0] = 0; a[1] = 1;
Flatten[{1,Table[a[2*n] = a[n]; a[2*n + 1] = a[n] + a[n + 1], {n, 0, 50}]}] (* Horst H. Manninger, Jun 09 2021 *)

{a(n) = if( n<1, n==0, n--; sum( k=0, n, binomial( n+k, n-k)%2))};

{a(n) = my(m); if( n<2, n>=0, m = 2^length( binary( n-1)); a(n - m/2) + a(m-n+1))}; /* Michael Somos, May 30 2005 */

from sympy import binomial
def a(n):
    return 1 if n<1 else sum(binomial(n + k - 1, 2*k) % 2 for k in range(n + 1))
print([a(n) for n in range(101)]) # Indranil Ghosh, Mar 22 2017

from functools import reduce
def A007306(n): return sum(reduce(lambda x,y:(x[0],sum(x)) if int(y) else (sum(x),x[1]),bin((n<<1)-1)[-1:2:-1],(1,0))) if n else 1 # Chai Wah Wu, May 18 2023

maxrow <- 6 # by choice
a <- c(1,2)
for(m in 0:maxrow) for(k in 1:2^m){
  a[2^(m+1)+k  ] <- a[2^m+k] + a[k]
  a[2^(m+1)-k+1] <- a[2^m+k]
}
a
# Yosu Yurramendi, Jan 05 2015

# Given n, compute directly a(n)
# by taking into account the binary representation of n-1
# aa <- function(n){
  b <- as.numeric(intToBits(n))
  l <- sum(b)
  m <- which(b == 1)-1
  d <- 1
  if(l > 1) for(j in 1:(l-1)) d[j] <- m[j+1]-m[j]+1
  f <- c(1,m[1]+2) # In A002487: f <- c(0,1)
  if(l > 1) for(j in 3:(l+1)) f[j] <- d[j-2]*f[j-1]-f[j-2]
  return(f[l+1])
}
# a(0) = 1, a(1) = 1, a(n) = aa(n-1)   n > 1
#
# Example
n <- 73
aa(n-1)
#
# Yosu Yurramendi, Dec 15 2016

@CachedFunction
def a(n):
    return a((odd_part(n-1)+1)/2)+a((odd_part(n)+1)/2) if n>1 else 1
[a(n) for n in (0..77)] # after Alessandro De Luca, Peter Luschny, May 20 2014

def A007306(n):
    if n == 0: return 1
    M = [1, 1]
    for b in (n-1).bits():
        M[b] = M[0] + M[1]
    return M[1]
print([A007306(n) for n in (0..77)]) # Peter Luschny, Nov 28 2017

(define (A007306 n) (if (zero? n) 1 (A002487 (+ n n -1)))) ;; Code for A002487 given in that entry. - Antti Karttunen, Mar 21 2017

Recurrence: a(0) to a(8) are 1, 1, 2, 3, 3, 4, 5, 5, 4; thereafter a(n) = a(n-2^p) + a(2^(p+1)-n+1), where 2^p < n <= 2^(p+1). [J. Hermes, Math. Ann., 1894; quoted by Dickson, Vol. 1, p. 158] - N. J. A. Sloane, Mar 24 2019
a(4*n) = -a(n)+2*a(2*n); a(4*n+1) = -a(n)+a(2*n)+a(2*n+1); a(4*n+2)=a(n)-a(2*n)+2*a(2*n+1); a(4*n+3) = 4*a(n)-4*a(2*n)+3*a(2*n+1). Thus a(n) is a 2-regular sequence. - Jeffrey Shallit, Dec 26 2024
For n > 0, a(n) = A002487(n-1) + A002487(n) = A002487(2*n-1).
a(0) = 1; a(n) = Sum_{k=0..n-1} C(n-1+k, n-1-k) mod 2, n > 0. - Benoit Cloitre, Jun 20 2003
a(n+1) = Sum_{k=0..n} binomial(2*n-k, k) mod 2; a(n) = 0^n + Sum_{k=0..n-1} binomial(2(n-1)-k, k) mod 2. - Paul Barry, Dec 11 2004
a(n) = Sum_{k=0..n} C(n+k,2*k) mod 2. - Paul Barry, Jun 12 2006
a(0) = a(1) = 1; a(n) = a(A003602(n-1)) + a(A003602(n)), n > 1. - Alessandro De Luca, May 08 2014
a(n) = A007305(n+(2^m-1)), m=A029837(n), n=1,2,3,... . - Yosu Yurramendi, Jul 04 2014
a(n) = A007305(2^(m+1)-n) - A007305(2^m-n), m >= (A029837(n)+1), n=1,2,3,... - Yosu Yurramendi, Jul 05 2014
a(2^m) = m+1, a(2^m+1) = m+2 for m >= 0. - Yosu Yurramendi, Jan 01 2015
a(n+2) = A007305(n+2) + A047679(n) n >= 0. - Yosu Yurramendi, Mar 30 2016
a(2^m+2^r+k) = a(2^r+k)(m-r+1) - a(k), m >= 2, 0 <= r <= m-1, 0 <= k < 2^r. Example: a(73) = a(2^6+2^3+1) = a(2^3+1)*(6-3+1) - a(1) = 5*4 - 1 = 19 . - Yosu Yurramendi, Jul 19 2016
From Antti Karttunen, Mar 21 2017 & Apr 12 2017: (Start)
For n > 0, a(n) = A001222(A277324(n-1)) = A001222(A260443(n-1)*A260443(n)).
The following decompositions hold for all n > 0:
a(n) = A277328(n-1) + A284009(n-1).
a(n) = A283986(n) + A283988(n) = A283987(n) + 2*A283988(n).
a(n) = 2*A284265(n-1) + A284266(n-1).
a(n) = A284267(n-1) + A284268(n-1).
a(n) = A284565(n-1) + A284566(n-1).
a(n) = A285106(n-1) + A285108(n-1) = A285107(n-1) + 2*A285108(n-1). (End)
a(A059893(n)) = a(n+1) for n > 0. - Yosu Yurramendi, May 30 2017
a(n) = A287731(n) + A287732(n) for n > 0. - I. V. Serov, Jun 09 2017
a(n) = A287896(n) + A288002(n) for n > 1.
a(n) = A287896(n-1) + A002487(n-1) - A288002(n-1) for n > 1.
a(n) = a(n-1) + A002487(n-1) - 2*A288002(n-1) for n > 1. - I. V. Serov, Jun 14 2017
From Yosu Yurramendi, May 14 2019: (Start)
For m >= 0, M >= m, 0 <= k < 2^m,
a((2^(m+1) + A119608(2^m+k+1))*2^(M-m) - A000035(2^m+k)) =
a((2^(m+2) - A119608(2^m+k+1))*2^(M-m) - A000035(2^m+k)-1) =
a(2^(M+2) - (2^m+k)) = a(2^(M+1) + (2^m+k) + 1) =
a(2^m+k+1)*(M-m) + a(2^(m+1)+2^m+k+1). (End)
a(k) = sqrt(A007305(2^(m+1)+k)*A047679(2^(m+1)+k-2) - A007305(2^m+k)*A047679(2^m+k-2)), m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Jun 09 2019
G.f.: 1 + x * (1 + x) * Product_{k>=0} (1 + x^(2^k) + x^(2^(k+1))). - Ilya Gutkovskiy, Jul 19 2019
Conjecture: a(n) = a(n-1) + b(n-1) - 2*(a(n-1) mod b(n-1)) for n > 1 with a(0) = a(1) = 1 where b(n) = a(n) - b(n-1) for n > 1 with b(1) = 1. - Mikhail Kurkov, Mar 13 2022

Formula fixed and extended by Franklin T. Adams-Watters, Jul 07 2009

Incorrect Maple program removed by Johannes W. Meijer, Jun 05 2011

A071766 Denominator of the continued fraction expansion whose terms are the first-order differences of exponents in the binary representation of 4n, with the exponents of 2 being listed in descending order.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 5, 4, 5, 1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8, 1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8, 6, 9, 10, 11, 9, 12, 11, 13, 6, 9, 10, 11, 9, 12, 11, 13, 1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8, 6, 9, 10, 11, 9, 12, 11, 13

Offset: 0

Paul D. Hanna, Jun 04 2002

If the terms (n>0) are written as an array:
 1,
 1, 2,
 1, 2, 3, 3,
 1, 2, 3, 3, 4, 5, 4, 5,
 1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8,
 1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8, 6, 9, 10, 11, 9, 12, 11, 13, 6, 9,
then the sum of the m-th row is 3^m (m = 0,1,2,3,...), each column is constant and the terms are from A071585 (a(2^m+k) = A071585(k), k = 0,1,2,...).
If the rows are written in a right-aligned fashion:
                                                                                 1,
                                                                             1,  2,
                                                                     1,  2,  3,  3,
                                                       1, 2,  3,  3, 4,  5,  4,  5,
                          1, 2,  3,  3, 4,  5,  4,  5, 5, 7,  7,  8, 5,  7,  7,  8,
..., 7, 7, 8, 5, 7, 7, 8, 6, 9, 10, 11, 9, 12, 11, 13, 6, 9, 10, 11, 9, 12, 11, 13,
then each column is a Fibonacci sequence (a(2^(m+2)+k) = a(2^(m+1)+k) + a(2^m+k), m = 0,1,2,..., k = 0,1,2,...,2^m-1 with a_k(1) = A071766(k) and a_k(2) = A086593(k) being the first two terms of each column sequence). - Yosu Yurramendi, Jun 23 2014

			a(37) = 5 as it is the denominator of 17/5 = 3 + 1/(2 + 1/2), which is a continued fraction that can be derived from the binary expansion of 4*37 = 2^7 + 2^4 + 2^2; the binary exponents are {7, 4, 2}, thus the differences of these exponents are {3, 2, 2}; giving the continued fraction expansion of 17/5 = [3,2,2].
1, 2, 3, 3/2, 4, 5/2, 4/3, 5/3, 5, 7/2, 7/3, 8/3, 5/4, 7/5, 7/4, 8/5, 6, ...

Paul D. Hanna, Table of n, a(n) for n = 0..10000
Index entries for fraction trees

Cf. A071585, A086593.

{1}~Join~Table[Denominator@ FromContinuedFraction@ Append[Abs@ Differences@ #, Last@ #] &@ Log2[NumberExpand[4 n, 2] /. 0 -> Nothing], {n, 120}] (* Version 11, or *)
{1}~Join~Table[Denominator@ FromContinuedFraction@ Append[Abs@ Differences@ #, Last@ #] &@ Log2@ DeleteCases[# Reverse[2^Range[0, Length@ # - 1]] &@ IntegerDigits[4 n, 2], k_ /; k == 0], {n, 120}] (* Michael De Vlieger, Aug 15 2016 *)

blocklevel <- 6 # arbitrary
a <- 1
for(m in 0:blocklevel) for(k in 0:(2^(m-1)-1)){
  a[2^(m+1)+k]             <- a[2^m+k]
  a[2^(m+1)+2^(m-1)+k]     <- a[2^m+2^(m-1)+k]
  a[2^(m+1)+2^m+k]         <- a[2^(m+1)+k]     +  a[2^(m+1)+2^(m-1)+k]
  a[2^(m+1)+2^m+2^(m-1)+k] <- a[2^(m+1)+2^m+k]
}
a
# Yosu Yurramendi, Jul 11 2014

a(n) = A071585(m), where m = n - floor(log_2(n));
a(0) = 1, a(2^k) = 1, a(2^k + 1) = 2.
a(2^k - 1) = Fibonacci(k+1) = A000045(k+1).
a(2^m+k) = A071585(k), m=0,1,2,..., k=0,1,2,...,2^m-1. - Yosu Yurramendi, Jun 23 2014
a(2^m-k) = F_k(m), k=0,1,2,..., m > log_2(k). F_k(m) is a Fibonacci sequence, where F_k(1) = a(2^(m_0(k))-1-k), F_k(2) = a(2^(m_0(k)+1)-1-k), m_0(k) = ceiling(log_2(k+1))+1 = A070941(k). - Yosu Yurramendi, Jun 23 2014
a(n) = A002487(A059893(A233279(n))) = A002487(1+A059893(A006068(n))), n > 0. - Yosu Yurramendi, Sep 29 2021

A093873 Numerators in Kepler's tree of harmonic fractions.

Original entry on oeis.org

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

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

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

			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

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
Index entries for sequences related to music

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.

{-# 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

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

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

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, 0Yosu 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

A245326 Denominators of an enumeration system of the reduced nonnegative rational numbers.

Original entry on oeis.org

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

Offset: 1

Yosu Yurramendi, Jul 18 2014

A245325(n)/a(n) enumerates all the reduced nonnegative rational numbers exactly once.
If the terms (n>0) are written as an array (in a left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
1,
2, 1,
3, 3, 2,1,
5, 4, 5,4, 3, 3,2,1,
8, 7, 7,5, 8, 7,7,5, 5, 4, 5,4, 3, 3,2,1,
13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,
then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence. These Fibonacci sequences are equal to Fibonacci sequences from A...... except for the first terms of those sequences.
If the rows are written in a right-aligned fashion:
                                                                        1,
                                                                      2,1,
                                                                  3,3,2,1,
                                                          5,4,5,4,3,3,2,1,
                                          8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,
13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,
then each column is constant and the terms are from A071585 (a(2^m-1-k) = A071585(k), k = 0,1,2,...).
If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are permutations of terms of blocks from A002487 (Stern's diatomic series or the Stern-Brocot sequence), and, more precisely, the reverses of blocks of A071766 (a(2^m+k) = A071766(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). Moreover, each block is the bit-reversed permutation of the corresponding block of A245328.

Index entries for fraction trees

Cf. A245325, A002487, A071585, A071766, A273494.

Cf. A002487, A059893, A154435.

a(n) = my(A=1); for(i=0, logint(n, 2), if(bittest(2*n, i), A++, A=(A+1)/A)); denominator(A) \\ Mikhail Kurkov, Feb 20 2023

blocklevel <- 6 # arbitrary
a <- 1
for(m in 0:blocklevel) for(k in 0:(2^(m-1)-1)){
  a[2^(m+1)+k]             <- a[2^m+k] + a[2^m+2^(m-1)+k]
  a[2^(m+1)+2^(m-1)+k]     <- a[2^(m+1)+k]
  a[2^(m+1)+2^m+k]         <- a[2^m+k]
  a[2^(m+1)+2^m+2^(m-1)+k] <- a[2^m+2^(m-1)+k]
}
a

a(n) = A002487(1+A059893(A180200(n))) = A002487(A059893(A154435(n))). - Yosu Yurramendi, Sep 20 2021

A086592 Denominators in left-hand half of Kepler's tree of fractions.

Original entry on oeis.org

2, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 7, 7, 8, 8, 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, 17, 17, 19, 19, 14, 14, 19, 19, 18, 18, 21, 21, 8, 8, 13, 13, 16, 16, 17, 17, 17, 17, 22, 22, 19, 19, 23

Offset: 1

Antti Karttunen, Aug 28 2003

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).
Level n of the left-hand half of the tree consists of 2^(n-1) 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; ... .
The right-hand half is identical to the left-hand half. - Michel Dekking, Oct 05 2017
n>1 occurs in this sequence phi(n) = A000010(n) times, as it occurs in A007306 (Franklin T. Adams-Watters' comment), that is the sequence obtained by adding numerator and denominator in the Calkin-Wilf enumeration system of positive rationals. A020650(n)/A020651(n) is also an enumeration system of all positive rationals (Yu-Ting system), and in each level m >= 0 (ranks between 2^m and 2^(m+1)-1) rationals are the same in both systems. Thus a(n) has the same terms in each level as A007306. The same property occurs in all numerator+denominator sequences of enumeration systems of positive rationals, as, for example, A007306 (A007305+A047679), A071585 (A229742+A071766), and A268087 (A162909+A162910). - Yosu Yurramendi, Apr 06 2016

Johannes Kepler, Mysterium cosmographicum, Tuebingen, 1596, 1621, Caput XII.
Johannes Kepler, Harmonice Mundi, Linz, 1619, Liber III, Caput II.
Johannes Kepler, The Harmony of the World [1619], trans. E. J. Aiton, A. M. Duncan and J. V. Field, American Philosophical Society, Philadelphia, 1997, p. 163.

Johannes Kepler, Harmonices mundi libri V ... (A Latin original scanned in Internet Archive. The fraction-tree is illustrated on the page 27 of the third book (Liber III), which is on the page 117 of the PDF-document.)
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/A086592-tree).
OEIS Wiki, Historical sequences
Pelegrí Viader, Jaume Paradís and Lluís Bibiloni, A New Light on Minkowski's ?(x) Function, J. Number Theory, 73 (2) (1998), 212-227. See p. 215.
Index entries for fraction trees
Index entries for sequences related to music

Bisection of A020650.
See A093873/A093875 for the full tree.
A020651 gives the numerators. Bisection: A086593. Cf. A002487, A004169.

(* b = A020650 *) b[1] = 1; b[2] = 2; b[3] = 1; b[n_] := b[n] = Switch[ Mod[n, 4], 0, b[n/2 + 1] + b[n/2], 1, b[(n - 1)/2 + 1], 2, b[(n - 2)/2 + 1] + b[(n - 2)/2], 3, b[(n - 3)/2]]; a[n_] := b[2n]; Array[a, 100] (* Jean-François Alcover, Jan 22 2016 *)

maxlevel <- 15
d <- c(1,2)
for(m in 0:maxlevel)
for(k in 1:2^m) {
   d[2^(m+1)    +k] <- d[k] + d[2^m+k]
   d[2^(m+1)+2^m+k] <- d[2^(m+1)+k]
}
b <- vector()
for(m in 0:maxlevel) for(k in 0:(2^m-1)) b[2^m+k] <- d[2^(m+1)+k]
a <- vector()
for(n in 1:2^maxlevel) {a[2*n-1] <- b[n]; a[2*n] <- b[n+1]}
a[1:128]
# Yosu Yurramendi, May 16 2018

a(n) = A020650(n) + A020651(n) = A020650(2n).
a(n) = A071585(A059893(n)), a(A059893(n)) = A071585(n), n > 0. - Yosu Yurramendi, May 30 2017
a(2*n-1) = A086593(n); a(2*n) = A086593(n+1), n > 0. - Yosu Yurramendi, May 16 2018
a(n) = A007306(A231551(n)), n > 0. - Yosu Yurramendi, Aug 07 2021

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

A245325 Numerators of an enumeration system of the reduced nonnegative rational numbers.

Original entry on oeis.org

1, 1, 2, 2, 1, 3, 3, 3, 3, 2, 1, 5, 4, 5, 4, 5, 4, 5, 4, 3, 3, 2, 1, 8, 7, 7, 5, 8, 7, 7, 5, 8, 7, 7, 5, 8, 7, 7, 5, 5, 4, 5, 4, 3, 3, 2, 1, 13, 11, 12, 9, 11, 10, 9, 6, 13, 11, 12, 9, 11, 10, 9, 6, 13, 11, 12, 9, 11, 10, 9, 6, 13, 11, 12, 9, 11, 10, 9, 6, 8, 7, 7, 5, 8, 7, 7, 5, 5, 4, 5, 4, 3, 3, 2, 1, 21, 18, 19, 14, 19

Offset: 1

Yosu Yurramendi, Jul 18 2014

a(n)/A245326(n) enumerates all the reduced nonnegative rational numbers exactly once.
If the terms (n>0) are written as an array (in a left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
  1,
  1,2,
  2,1,3,3,
  3,3,2,1,5,4,5,4,
  5,4,5,4,3,3,2,1,8,7,7,5,8,7,7,5,
  8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,
then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence.
If the rows are written in a right-aligned fashion:
                                                                        1,
                                                                      1,2,
                                                                 2, 1,3,3,
                                                      3, 3, 2,1, 5, 4,5,4,
                                 5, 4, 5,4, 3, 3,2,1, 8, 7, 7,5, 8, 7,7,5,
8,7,7,5,8,7,7,5,5,4,5,4,3,3,2,1,13,11,12,9,11,10,9,6,13,11,12,9,11,10,9,6,
then each column is an arithmetic sequence. The differences of the arithmetic sequences give the sequence A071585 (a(2^(m+1)-1-k) - a(2^m-1-k) = A071585(k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).
If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are permutations of terms of blocks from A002487 (Stern's diatomic series or the Stern-Brocot sequence), and, more precisely, the reverses of blocks of A229742 (a(2^m+k) = A229742(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). Moreover, each block is the bit-reversed permutation of the corresponding block of A245327.

Index entries for fraction trees

Cf. A245326, A002487, A071585, A229742, A273494.

blocklevel <- 6 # arbitrary
a <- 1
for(m in 0:blocklevel) for(k in 0:(2^(m-1)-1)){
  a[2^(m+1)+k]             <- a[2^m+2^(m-1)+k]
  a[2^(m+1)+2^(m-1)+k]     <- a[2^m+k]
  a[2^(m+1)+2^m+k]         <- a[2^(m+1)+k] +  a[2^m+k]
  a[2^(m+1)+2^m+2^(m-1)+k] <- a[2^(m+1)+2^m+k]
}
a

a(n) = A002487(A059893(A180200(n))) = A002487(1+A059893(A154435(n))). - Yosu Yurramendi, Sep 20 2021

A093875 Denominators in Kepler's tree of harmonic fractions.

Original entry on oeis.org

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

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

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

			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

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for fraction trees

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

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

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)

A268087 a(n) = A162909(n) + A162910(n).

Original entry on oeis.org

2, 3, 3, 5, 4, 4, 5, 8, 7, 5, 7, 7, 5, 7, 8, 13, 11, 9, 12, 9, 6, 10, 11, 11, 10, 6, 9, 12, 9, 11, 13, 21, 18, 14, 19, 16, 11, 17, 19, 14, 13, 7, 11, 17, 13, 15, 18, 18, 15, 13, 17, 11, 7, 13, 14, 19, 17, 11, 16, 19, 14, 18, 21, 34, 29, 23, 31, 25, 17, 27, 30, 25, 23, 13, 20, 29, 22, 26, 31, 23, 19, 17, 22, 13, 8, 16, 17, 27

Offset: 1

Yosu Yurramendi, Jan 26 2016

If the terms (n>0) are written as an array (in a left-aligned fashion) with rows of length 2^m, m >= 0:
2,
3, 3,
5, 4, 4, 5,
8, 7, 5, 7, 7, 5, 7, 8,
13,11, 9,12, 9, 6,10,11,11,10,6, 9,12, 9,11,13,
21,18,14,19,16,11,17,19,14,13,7,11,17,13,15,18,18,15,13,17,11,7,13,14,19,17,11,16, ...
a(n) is palindromic in each level m >= 0 (ranks between 2^m and 2^(m+1)-1), because in each level m >= 0 A162910 is the reverse of A162909:
a(2^m + k) = a(2^(m+1) - 1 - k), m >= 0, 0 <= k < 2^m.
All columns have the Fibonacci sequence property: a(2^(m+2) + k) = a(2^(m+1) + k) + a(2^m + k), m >= 0, 0 <= k < 2^m (empirical observations).
a(2^m + k) = A162909(2^(m+2) + k), a(2^m + k) = A162909(2^(m+1)+ 2^m + k), a(2^m + k) = A162910(2^(m+1) + k), m >= 0, 0 <= k < 2^m (empirical observations).
a(n) = A162911(n) + A162912(n), where A162911(n)/A162912(n) is the bit reversal permutation of A162909(n)/A162910(n) in each level m >= 0 (empirical observations).
a(n) = A162911(2n+1), a(n) = A162912(2n) for n > 0 (empirical observations). n > 1 occurs in this sequence phi(n) = A000010(n) times, as it occurs in A007306 (Franklin T. Adams-Watters's comment), which is the sequence obtained by adding numerator and denominator in the Calkin-Wilf enumeration system of positive rationals. A162909(n)/A162910(n) is also an enumeration system of all positive rationals (Bird system), and in each level m >= 0 (ranks between 2^m and 2^(m+1)-1) rationals are the same in both systems. Thus a(n) has the same terms in each level as A007306.
The same property occurs in all numerator+denominator sequences of enumeration systems of positive rationals, as, for example, A007306 (A007305+A047679), A071585 (A229742+A071766), and A086592 (A020650+A020651).

			m = 3, k = 6: a(38) = 17, a(22) = 10, a(14) = 7.

Cf. A162909, A162910, A162911, A162912, A007306, A071585, A086592.

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

a(2^(m+2)+k) = a(2^(m+1)+k) + a(2^m+k) with m = 0, 1, 2, ... and 0 <= k < 2^m (empirical observation).
a(A059893(n)) = a(n) for n > 0. - Yosu Yurramendi, May 30 2017
From Yosu Yurramendi, May 14 2019: (Start)
Take the smallest m > 0 such that 0 <= k < 2^(m-1), and choose any M >= m,
a((1/3)*(  A016921(2^(m-1)+k)*4^(M-m)-1)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k  ).
a((1/3)*(2*A016921(2^(m-1)+k)*4^(M-m)-2)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k  ) + a(2^(m-1)+k).
a((1/3)*(  A016969(2^(m-1)+k)*4^(M-m)-2)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k+1).
a((1/3)*(2*A016969(2^(m-1)+k)*4^(M-m)-1)) = 2*a(2^(m-1)+k)*(M-m) + a(2^m+2*k+1) + a(2^(m-1)+k). (End)
a(n) = A007306(A258996(n)), n > 0. - Yosu Yurramendi, Jun 23 2021

cp's OEIS Frontend

A229742 a(n) = A071585(n) - A071766(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

R

Formula

A007306 Denominators of Farey tree fractions (i.e., the Stern-Brocot subtree in the range [0,1]).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Python

R

R

Sage

Sage

Scheme

Formula

Extensions

A071766 Denominator of the continued fraction expansion whose terms are the first-order differences of exponents in the binary representation of 4n, with the exponents of 2 being listed in descending order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

R

Formula

A093873 Numerators in Kepler's tree of harmonic fractions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A245326 Denominators of an enumeration system of the reduced nonnegative rational numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

R

Formula

A086592 Denominators in left-hand half of Kepler's tree of fractions.

Views

Author

Keywords

Comments

References

Links

Crossrefs