|
| |
|
|
A047679
|
|
Denominators in full Stern-Brocot tree.
|
|
40
|
|
|
|
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
|
Write n in binary; list run lengths; add 1 to last run length; make into continued fraction. Sequence gives denominator of fraction obtained.
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)
Looking at the plot, the sequence clearly shows a fractal structure. (The repeating pattern oddly resembles the [first completed] facade of the Sagrada Familia!) - Daniel Forgues, Nov 15 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = SternBrocotTreeDen(n) # n starting from 1.
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
|
|
|
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 */
(PARI) a(n) = my(n=n+1, x=1, y=1); for(i=0, logint(n, 2), if(bittest(n, i), [x, y]=[x+y, y], [x, y]=[x, x+y])); y \\ Mikhail Kurkov, Mar 10 2023
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,frac,nice,tabf,look
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
