The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60, we have over 367,000 sequences, and we’ve crossed 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A007305 Numerators of Farey (or Stern-Brocot) tree fractions. (Formerly M0113) 71
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,5 COMMENTS 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) and a(n+2) = A047679(A054429(n)); A153036(n+1) = floor(a(n+2)/A047679(n)). (End) 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 REFERENCES 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). LINKS 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 FORMULA 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 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 EXAMPLE 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, ... MAPLE SternBrocotTreeNum := proc(n) option remember; local msb, r; if(n < 2) then RETURN(n); fi; msb := floor_log_2(n); r := n - (2^msb); if(floor_log_2(r) = (msb-1)) then RETURN(SternBrocotTreeNum(r) + SternBrocotTreeNum(((3*(2^(msb-1)))-r)-1)); else RETURN(SternBrocotTreeNum((2^(msb-1))+r)); fi; end; # Antti Karttunen, Mar 19 2000 [Broken program - N. J. A. Sloane, Aug 05 2020] MATHEMATICA 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 *) PROG (R) 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 CROSSREFS Cf. A007306, A006842, A006843, A047679, A054424, A057114, A152975. Sequence in context: A035531 A118977 A071766 * A112531 A100002 A348330 Adjacent sequences: A007302 A007303 A007304 * A007306 A007307 A007308 KEYWORD nonn,frac,tabf,nice,look AUTHOR N. J. A. Sloane STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 2 06:18 EST 2023. Contains 367509 sequences. (Running on oeis4.)