%I A007305 M0113
%S A007305 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,
%T A007305 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,
%U A007305 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 A007305 Numerators of Farey (or Stern-Brocot) tree fractions.
%C A007305 Contribution from Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               Dec 22 2008: (Start)
%C A007305 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 A007305 a(A054429(n)+2) = A047679(n) and a(n+2) = A047679(A054429(n));
%C A007305 A153036(n) = floor(a(n+2)/A047679(n)). (End)
%D A007305 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, 
               Reading, MA, 1990, p. 117.
%D A007305 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 
               3rd ed., Oxford Univ. Press, 1954, p. 23.
%D A007305 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 A007305 W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 
               2 vols., 1956, Vol. 1, p. 154.
%D A007305 G. Melancon, Lyndon factorization of sturmian words, Discr. Math., 210 
               (2000), 137-149.
%D A007305 I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 
               2nd ed., Wiley, NY, 1966, p. 141.
%D A007305 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A007305 T. D. Noe, <a href="b007305.txt">Table of n, a(n) for n=0..4096</a>
%H A007305 A. Bogomolny, <a href="http://www.cut-the-knot.org/blue/Stern.shtml">
               Stern-Brocot Tree</a>
%H A007305 A. Bogomolny, <a href="http://www.cut-the-knot.org/blue/SB_props.shtml">
               Inspiration for Maple code</a>
%H A007305 G. A. Jones, <a href="http://www.mat.univie.ac.at/~slc/opapers/s18jones.html">
               The Farey graph</a>
%H A007305 N. J. A. Sloane, <a href="stern_brocot.html">Stern-Brocot or Farey Tree</
               a>
%H A007305 <a href="Sindx_St.html#Stern">Index entries for sequences related to 
               Stern's sequences</a>
%F A007305 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, ...
%e A007305 [ 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 A007305 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;
%t A007305 Contribution from Peter Luschny (peter(AT)luschny.de), Apr 27 2009: (Start)
%t A007305 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 A007305(n) = Flatten[Append[{0,1},Table[Map[First,sbt[i]],{i,0,5}]]]
%t A007305 A047679(n) = Flatten[Table[Map[Last,sbt[i]],{i,0,5}]] (End)
%Y A007305 Cf. A007306, A006842, A006843, A047679, A054424, A057114.
%Y A007305 A152975. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               Dec 22 2008]
%Y A007305 Sequence in context: A035531 A118977 A071766 this_sequence A112531 A100002 
               A057041
%Y A007305 Adjacent sequences: A007302 A007303 A007304 this_sequence A007306 A007307 
               A007308
%K A007305 nonn,frac,tabf,nice
%O A007305 0,5
%A A007305 N. J. A. Sloane (njas(AT)research.att.com).
%E A007305 Maple code from Antti Karttunen, Mar 19 2000