|
%I M0113 #102 Apr 18 2023 09:44:32
%S 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,
%T 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,
%U 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
%N Numerators of Farey (or Stern-Brocot) tree fractions.
%C From _Reinhard Zumkeller_, Dec 22 2008: (Start)
%C 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);
%C a(A054429(n)+2) = A047679(n) and a(n+2) = A047679(A054429(n));
%C A153036(n+1) = floor(a(n+2)/A047679(n)). (End)
%C From _Yosu Yurramendi_, Jun 25 2014: (Start)
%C 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 1,
%C 1,2,
%C 1,2,3,3,
%C 1,2,3,3,4,5,5,4,
%C 1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,
%C 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,
%C 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).
%C If the rows are written in a right-aligned fashion:
%C 1,
%C 1,2,
%C 1, 2,3,3,
%C 1, 2, 3, 3, 4, 5,5,4,
%C 1,2, 3, 3, 4, 5, 5,4,5, 7, 8, 7, 7, 8,7,5,
%C 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,
%C 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)
%C 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
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
%D 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.
%D W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
%D I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A007305/b007305.txt">Table of n, a(n) for n=0..4096</a>
%H A. Bogomolny, <a href="http://www.cut-the-knot.org/blue/Stern.shtml">Stern-Brocot Tree</a>
%H A. Bogomolny, <a href="http://www.cut-the-knot.org/blue/SB_props.shtml">Inspiration for Maple code</a>
%H A. Brocot, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k1661912">Calcul des rouages par approximation, nouvelle méthode</a>, Revue Chonométrique 3, 186-194, 1861.
%H G. A. Jones, <a href="http://www.mat.univie.ac.at/~slc/opapers/s18jones.html">The Farey graph</a>, Séminaire Lotharingien de Combinatoire, B18e (1987), 2 pp.
%H Shin-ichi Katayama, <a href="https://www-math.ias.tokushima-u.ac.jp/journal/2013/Katayama47.pdf">Modified Farey trees and Pythagorean triples</a>, Journal of mathematics, the University of Tokushima, 47, 2013.
%H G. Melançon, <a href="https://doi.org/10.1016/S0012-365X(99)00123-5">Lyndon factorization of sturmian words</a>, Discr. Math., 210 (2000), 137-149.
%H Hugo Pfoertner, <a href="https://oeis.org/plot2a?name1=A007305&name2=A007306&tform1=untransformed&tform2=untransformed&shift=0&radiop1=ratio&drawpoints=true">Ratio A007305(n)/A007306(n) vs n</a>, using Plot 2.
%H N. J. A. Sloane, <a href="/stern_brocot.html">Stern-Brocot or Farey Tree</a>
%H Noam Zimhoni, <a href="https://arxiv.org/abs/1904.11782">A forest of Eisensteinian triplets</a>, arXiv:1904.11782 [math.NT], 2019.
%H <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%F 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, ...
%F From _Yosu Yurramendi_, Jun 25 2014: (Start)
%F For m = 1,2,3,..., and k = 0,1,2,...,2^(m-1)-1, with a(1)=1:
%F a(2^m+k) = a(2^(m-1)+k);
%F a(2^m+2^(m-1)+k) = a(2^(m-1)+k) + a(2^m-k-1). (End)
%F 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
%F 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
%F From _Yosu Yurramendi_, Jan 01 2015: (Start)
%F a(2^m+2^q-1) = q+1, q = 0, 1, 2,..., m = q, q+1, q+2,...
%F a(2^m+2^q) = q+2, q = 0, 1, 2,..., m = q+1, q+2, q+3,... (End)
%F a(2^m+k) = A007306(k+1), m >= 0, 0 <= k < 2*m. - _Yosu Yurramendi_, May 20 2019
%F a(n) = A002487(A059893(n)), n > 0. - _Yosu Yurramendi_, Sep 29 2021
%e 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, ...
%e 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, ...
%p 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]
%t 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]]]]
%t A007305(n) = Flatten[Append[{0,1},Table[Map[First,sbt[i]],{i,0,5}]]]
%t A047679(n) = Flatten[Table[Map[Last,sbt[i]],{i,0,5}]]
%t (* _Peter Luschny_, Apr 27 2009 *)
%o (R)
%o a <- 1
%o for(m in 1:6) for(k in 0:(2^(m-1)-1)) {
%o a[2^m+ k] <- a[2^(m-1)+k]
%o a[2^m+2^(m-1)+k] <- a[2^(m-1)+k] + a[2^m-k-1]
%o }
%o a
%o # _Yosu Yurramendi_, Jun 25 2014
%Y Cf. A007306, A006842, A006843, A047679, A054424, A057114, A152975.
%K nonn,frac,tabf,nice,look
%O 0,5
%A _N. J. A. Sloane_
|
