|
| |
|
|
A047679
|
|
Denominators in full Stern-Brocot tree.
|
|
36
|
|
|
|
1, 2, 1, 3, 3, 2, 1, 4, 5, 5, 4, 3, 3, 2, 1, 5, 7, 8, 7, 7, 8, 7, 5, 4, 5, 5, 4, 3, 3, 2, 1, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11, 10, 11, 9, 6, 5, 7, 8, 7, 7, 8, 7, 5, 4, 5, 5, 4, 3, 3, 2, 1, 7, 11, 14, 13, 15, 18, 17, 13, 14, 19, 21, 18, 17, 19, 16, 11, 11, 16, 19, 17, 18
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Numerators are A007305.
Write n in binary; list run lengths; add 1 to last run length; make into continued fraction. Sequence gives denominator of fraction obtained.
From Reinhard Zumkeller, Dec 22 2008: (Start)
For n > 1: a(n) = if A025480(n-1) != 0 and A025480(n) != 0 then = a(A025480(n-1)) + a(A025480(n)) else if A025480(n)=0 then a(A025480(n-1))+0 else 1+a(A025480(n-1));
a(n) = A007305(A054429(n)+2) and a(A054429(n)) = A007305(n+2);
A153036(n) = floor(A007305(n+2)/a(n)). (End)
From Yosu Yurramendi, Jun 25 2014 and Jun 30 2014: (Start)
If the terms are written as an array a(m, k) = a(2^(m-1)-1+k) with m >= 1 and k = 0, 1, ..., 2^(m-1)-1:
1,
2,1,
3,3, 2, 1,
4,5, 5, 4, 3, 3, 2,1,
5,7, 8, 7, 7, 8, 7,5,4, 5, 5, 4, 3, 3,2,1,
6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,5,7,8,7,7,8,7,5,4,5,5,4,3,3,2,1,
then the sum of the m-th row is 3^(m-1), and each column is an arithmetic sequence. The differences of these arithmetic sequences give the sequence A007306(k+1). The first terms of columns are 1 for k = 0 and a(k-1) for k >= 1.
In a row reversed version A(m, k) = a(m, m-(k+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,12,9,9,12,13,11,10,11,9,6
each column k >= 0 is constant, namely A007306(k+1).
This row reversed version coincides with the array for A007305 (see the Jun 25 2014 comment there). (End)
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Stern-Brocot or Farey Tree
Index entries for fraction trees
Index entries for sequences related to Stern's sequences
|
|
|
FORMULA
|
a(n) = SternBrocotTreeDen(n) # n starting from 1.
From Yosu Yurramendi, Jul 02 2014: (Start)
For m >0 and 0 <= k < 2^(m-1), with a(0)=1, a(1)=2:
a(2^m+k-1) = a(2^(m-1)+k-1) + a((2^m-1)-k-1);
a(2^m+2^(m-1)+k-1) = a(2^(m-1)+k-1). (End)
a(2^m-2^q ) = q+1, q >= 0, m > q
a(2^m-2^q-1) = q+2, q >= 0, m > q+1. - Yosu Yurramendi, Jan 01 2015
a(2^(m+1)-1-k) = A007306(k+1), m >= 0, 0 <= k <= 2^m. - Yosu Yurramendi, May 20 2019
|
|
|
EXAMPLE
|
E.g., 57->111001->[ 3,2,1 ]->[ 3,2,2 ]->3 + 1/(2 + 1/(2) ) = 17/2. For n=1,2, ... we get 2, 3/2, 3, 4/3, 5/3, 5/2, 4, 5/4, 7/5, 8/5, ...
1; 2,1; 3,3,2,1; 4,5,5,4,3,3,2,1; ....
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
|
SternBrocotTreeDen := n -> SternBrocotTreeNum(((3*(2^floor_log_2(n)))-n)-1); # SternBrocotTreeNum given in A007305 and (((3*(2^floor_log_2(n)))-n)-1) is equal to A054429[n].
|
|
|
MATHEMATICA
|
CFruns[ n_Integer ] := Fold[ #2+1/#1&, Infinity, Reverse[ MapAt[ #+1&, Length/@Split[ IntegerDigits[ n, 2 ] ], {-1} ] ] ]
(* second program: *)
a[n_] := Module[{LL = Length /@ Split[IntegerDigits[n, 2]]}, LL[[-1]] += 1; FromContinuedFraction[LL] // Denominator]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 25 2016 *)
|
|
|
PROG
|
(PARI) {a(n) = local(v, w); v = binary(n++); w = [1]; for( n=2, #v, if( v[n] != v[n-1], w = concat(w, 1), w[#w]++)); w[#w]++; contfracpnqn(w)[2, 1]} /* Michael Somos, Jul 22 2011 */
(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-k-1]
a[2^m+2^(m-1)+k] = a[2^(m-1)+k]
}
a
# Yosu Yurramendi, Dec 31 2014
|
|
|
CROSSREFS
|
Cf. A007305, A007306, A054424, A152976.
Sequence in context: A302555 A262209 A324338 * A179480 A245326 A241534
Adjacent sequences: A047676 A047677 A047678 * A047680 A047681 A047682
|
|
|
KEYWORD
|
nonn,easy,frac,nice,tabf
|
|
|
AUTHOR
|
Wouter Meeussen
|
|
|
EXTENSIONS
|
Edited by Wolfdieter Lang, Mar 31 2015
|
|
|
STATUS
|
approved
|
| |
|
|
