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

 

Logo


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

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)

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)

From Yosu Yurramendi, Jun 30 2014: (Start)

If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are the reverses of 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).

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

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

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

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

Contribution 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

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

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 A227909

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 | 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 October 23 12:58 EDT 2014. Contains 248464 sequences.