login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007305 Numerators of Farey (or Stern-Brocot) tree fractions.
(Formerly M0113)
38
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

Contribution 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) = floor(a(n+2)/A047679(n)). (End)

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.

G. Melancon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.

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

G. A. Jones, The Farey graph

N. J. A. Sloane, Stern-Brocot or Farey Tree

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

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;

MATHEMATICA

Contribution from Peter Luschny, Apr 27 2009: (Start)

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}]] (End)

CROSSREFS

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

Sequence in context: A035531 A118977 A071766 * A112531 A100002 A227909

Adjacent sequences:  A007302 A007303 A007304 * A007306 A007307 A007308

KEYWORD

nonn,frac,tabf,nice,look

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Maple code from Antti Karttunen, Mar 19 2000

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 19 14:44 EDT 2014. Contains 240761 sequences.