|
|
A007305
|
|
Numerators of Farey (or Stern-Brocot) tree fractions.
(Formerly M0113)
|
|
73
|
|
|
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
|
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
|
G. A. Jones, The Farey graph, Séminaire Lotharingien de Combinatoire, B18e (1987), 2 pp.
|
|
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, ...
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+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)
|
|
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
|
A007305 := proc(n) local b; b := proc(n) option remember; local msb, r;
if n < 3 then return 1 fi; msb := ilog2(n); r := n - 2^msb;
if ilog2(r) = msb - 1 then b(r) + b(3*2^(msb-1) - r - 1) else b(2^(msb - 1) + r) fi end: if n = 0 then 0 else b(n-1) fi end: # Antti Karttunen, Mar 19 2000 [Corrected and rewritten by Peter Luschny, Apr 24 2024]
|
|
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}]]
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|