A153036 -id:A153036 - cp's OEIS frontend

A007305 Numerators of Farey (or Stern-Brocot) tree fractions.

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

Offset: 0

N. J. A. Sloane

From Yosu Yurramendi, Jun 25 2014: (Start)
If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
   1,
   1,2,
   1,2,3,3,
   1,2,3,3,4,5,5,4,
   1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,
   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,
then the sum of the m-th row is 3^m (m = 0,1,2,), each column k is constant, and the constants are from A007306, denominators of Farey (or Stern-Brocot) tree fractions (see formula).
If the rows are written in a right-aligned fashion:
                                                                          1,
                                                                        1,2,
                                                                   1, 2,3,3,
                                                       1, 2, 3, 3, 4, 5,5,4,
                                  1,2, 3, 3, 4, 5, 5,4,5, 7, 8, 7, 7, 8,7,5,
  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,
then each column is an arithmetic sequence. The differences of the arithmetic sequences also give the sequence A007306 (see formula). The first terms of columns are from A007305 itself (a(A004761(n+1)) = a(n), n>0), and the second ones from A049448 (a(A004761(n+1)+2^A070941(n)) = A049448(n), n>0). (End)
If the sequence is considered in blocks of length 2^m, m = 0,1,2,..., the blocks are the reverse of the blocks of A047679: (a(2^m+1+k) = A047679(2^(m+1)-2-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). - Yosu Yurramendi, Jun 30 2014

			A007305/A007306 = [ 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, ...
Another version of Stern-Brocot is A007305/A047679 = 1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, 1/4, 4/3, 3/4, 5/2, 2/5, 5/3, 3/5, 5, 1/5, 5/4, 4/5, ...

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
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.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..4096
A. Bogomolny, Stern-Brocot Tree
A. Bogomolny, Inspiration for Maple code
A. Brocot, Calcul des rouages par approximation, nouvelle méthode, Revue Chonométrique 3, 186-194, 1861.
G. A. Jones, The Farey graph, Séminaire Lotharingien de Combinatoire, B18e (1987), 2 pp.
Shin-ichi Katayama, Modified Farey trees and Pythagorean triples, Journal of mathematics, the University of Tokushima, 47, 2013.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
Hugo Pfoertner, Ratio A007305(n)/A007306(n) vs n, using Plot 2.
N. J. A. Sloane, Stern-Brocot or Farey Tree
Noam Zimhoni, A forest of Eisensteinian triplets, arXiv:1904.11782 [math.NT], 2019.
Index entries for fraction trees
Index entries for sequences related to Stern's sequences

Cf. A007306, A006842, A006843, A047679, A054424, A057114, A152975.

A007305 := proc(n) local b; b := proc(n) option remember; local msb, r;
if n < 3 then return 1 fi; msb := ilog2(n); r := n - 2^msb;
if ilog2(r) = msb - 1 then b(r) + b(3*2^(msb-1) - r - 1) else b(2^(msb - 1) + r) fi end: if n = 0 then 0 else b(n-1) fi end: # Antti Karttunen, Mar 19 2000 [Corrected and rewritten by Peter Luschny, Apr 24 2024]
seq(A007305(n), n = 0..92);

sbt[n_] := Module[{R,L,Y}, R={{1,0},{1,1}}; L={{1,1},{0,1}}; Y={{1,0},{0,1}}; w[b_] := Fold[ #1.If[ #2 == 0,L,R] &,Y,b]; u[a_] := {a[[2,1]]+a[[2,2]],a[[1,1]]+a[[1,2]]}; Map[u,Map[w,Tuples[{0,1},n]]]]
A007305(n) = Flatten[Append[{0,1},Table[Map[First,sbt[i]],{i,0,5}]]]
A047679(n) = Flatten[Table[Map[Last,sbt[i]],{i,0,5}]]
(* Peter Luschny, Apr 27 2009 *)

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

a(n) = SternBrocotTreeNum(n-1) # n starting from 2 gives the sequence from 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 5, 5, 4, 1, ...
From Reinhard Zumkeller, Dec 22 2008: (Start)
For n > 1: a(n+2) = if A025480(n-1) != 0 and A025480(n) != 0 then a(A025480(n-1)+2) + a(A025480(n)+2) else if A025480(n)=0 then a(A025480(n-1)+2)+1 else 0 + a(A025480(n-1)+2).
a(A054429(n)+2) = A047679(n).
a(n+2) = A047679(A054429(n)).
A153036(n+1) = floor(a(n+2)/A047679(n)). (End)
From Yosu Yurramendi, Jun 25 2014: (Start)
For m = 1,2,3,..., and k = 0,1,2,...,2^(m-1)-1, with a(1)=1:
a(2^m+k) = a(2^(m-1)+k);
a(2^m+2^(m-1)+k) = a(2^(m-1)+k) + a(2^m-k-1). (End)
a(2^(m+2)-k) = A007306(2^(m+1)-k), m=0,1,2,..., k=0,1,2,...,2^m-1. - Yosu Yurramendi, Jul 04 2014
a(2^(m+1)+2^m+k) - a(2^m+k) = A007306(2^m-k+1), m=1,2,..., k=1,2,...,2^(m-1). - Yosu Yurramendi, Jul 05 2014
From Yosu Yurramendi, Jan 01 2015: (Start)
a(2^m+2^q-1) = q+1, q = 0, 1, 2,..., m = q, q+1, q+2,...
a(2^m+2^q)   = q+2, q = 0, 1, 2,..., m = q+1, q+2, q+3,... (End)
a(2^m+k) = A007306(k+1), m >= 0, 0 <= k < 2*m.  - Yosu Yurramendi, May 20 2019
a(n) = A002487(A059893(n)), n > 0. - Yosu Yurramendi, Sep 29 2021

A047679 Denominators in full Stern-Brocot tree.

Original entry on oeis.org

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

Offset: 0

Wouter Meeussen

Numerators are A007305.
Write n in binary; list run lengths; add 1 to last run length; make into continued fraction. Sequence gives denominator of fraction obtained.
From Reinhard Zumkeller, Dec 22 2008: (Start)
  For n > 1: a(n) = if A025480(n-1) != 0 and A025480(n) != 0 then = a(A025480(n-1)) + a(A025480(n)) else if A025480(n)=0 then a(A025480(n-1))+0 else 1+a(A025480(n-1));
  a(n) = A007305(A054429(n)+2) and a(A054429(n)) = A007305(n+2);
  A153036(n+1) = floor(A007305(n+2)/a(n)). (End)
From Yosu Yurramendi, Jun 25 2014 and Jun 30 2014: (Start)
If the terms are written as an array a(m, k) = a(2^(m-1)-1+k) with m >= 1 and k = 0, 1, ..., 2^(m-1)-1:
 1,
 2,1,
 3,3, 2, 1,
 4,5, 5, 4, 3, 3, 2,1,
 5,7, 8, 7, 7, 8, 7,5,4, 5, 5, 4, 3, 3,2,1,
 6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,5,7,8,7,7,8,7,5,4,5,5,4,3,3,2,1,
then the sum of the m-th row is 3^(m-1), and each column is an arithmetic sequence. The differences of these arithmetic sequences give the sequence A007306(k+1). The first terms of columns are 1 for k = 0 and a(k-1) for k >= 1.
In a row reversed version A(m, k) = a(m, m-(k+1)):
 1
 1,2
 1,2,3,3,
 1,2,3,3,4,5,5,4
 1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5
 1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,12,9,9,12,13,11,10,11,9,6
each column k >= 0 is constant, namely A007306(k+1).
This row reversed version coincides with the array for A007305 (see the Jun 25 2014 comment there). (End)
Looking at the plot, the sequence clearly shows a fractal structure. (The repeating pattern oddly resembles the [first completed] facade of the Sagrada Familia!) - Daniel Forgues, Nov 15 2019

			E.g., 57->111001->[ 3,2,1 ]->[ 3,2,2 ]->3 + 1/(2 + 1/(2) ) = 17/2. For n=1,2, ... we get 2, 3/2, 3, 4/3, 5/3, 5/2, 4, 5/4, 7/5, 8/5, ...
1; 2,1; 3,3,2,1; 4,5,5,4,3,3,2,1; ....
Another version of Stern-Brocot is A007305/A047679 = 1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, 1/4, 4/3, 3/4, 5/2, 2/5, 5/3, 3/5, 5, 1/5, 5/4, 4/5, ...

Alois P. Heinz, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Stern-Brocot or Farey Tree
Index entries for fraction trees
Index entries for sequences related to Stern's sequences

Cf. A007305, A007306, A054424, A152976.

CFruns[ n_Integer ] := Fold[ #2+1/#1&, Infinity, Reverse[ MapAt[ #+1&, Length/@Split[ IntegerDigits[ n, 2 ] ], {-1} ] ] ]
(* second program: *)
a[n_] := Module[{LL = Length /@ Split[IntegerDigits[n, 2]]}, LL[[-1]] += 1; FromContinuedFraction[LL] // Denominator]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 25 2016 *)

{a(n) = local(v, w); v = binary(n++); w = [1]; for( n=2, #v, if( v[n] != v[n-1], w = concat(w, 1), w[#w]++)); w[#w]++; contfracpnqn(w)[2, 1]} /* Michael Somos, Jul 22 2011 */

a <- 1
for(m in 1:6) for(k in 0:(2^(m-1)-1)) {
  a[2^m+        k] = a[2^(m-1)+k] + a[2^m-k-1]
  a[2^m+2^(m-1)+k] = a[2^(m-1)+k]
}
a
# Yosu Yurramendi, Dec 31 2014

a(n) = SternBrocotTreeDen(n) # n starting from 1.
From Yosu Yurramendi, Jul 02 2014: (Start)
For m >0 and 0 <= k < 2^(m-1), with a(0)=1, a(1)=2:
a(2^m+k-1) = a(2^(m-1)+k-1) + a((2^m-1)-k-1);
a(2^m+2^(m-1)+k-1) = a(2^(m-1)+k-1). (End)
a(2^m-2^q  ) = q+1, q >= 0, m > q
a(2^m-2^q-1) = q+2, q >= 0, m > q+1. - Yosu Yurramendi, Jan 01 2015
a(2^(m+1)-1-k) = A007306(k+1), m >= 0, 0 <= k <= 2^m. - Yosu Yurramendi, May 20 2019
a(n) = A002487(1+A059893(n)), n > 0. - Yosu Yurramendi, Sep 29 2021

Edited by Wolfdieter Lang, Mar 31 2015

cp's OEIS Frontend

A007305 Numerators of Farey (or Stern-Brocot) tree fractions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

R

Formula