login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047679 Denominators in full Stern-Brocot tree. 40

%I #93 Mar 10 2023 09:10:37

%S 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,

%T 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,

%U 11,14,13,15,18,17,13,14,19,21,18,17,19,16,11,11,16,19,17,18

%N Denominators in full Stern-Brocot tree.

%C Numerators are A007305.

%C Write n in binary; list run lengths; add 1 to last run length; make into continued fraction. Sequence gives denominator of fraction obtained.

%C From _Reinhard Zumkeller_, Dec 22 2008: (Start)

%C 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));

%C a(n) = A007305(A054429(n)+2) and a(A054429(n)) = A007305(n+2);

%C A153036(n+1) = floor(A007305(n+2)/a(n)). (End)

%C From _Yosu Yurramendi_, Jun 25 2014 and Jun 30 2014: (Start)

%C 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:

%C 1,

%C 2,1,

%C 3,3, 2, 1,

%C 4,5, 5, 4, 3, 3, 2,1,

%C 5,7, 8, 7, 7, 8, 7,5,4, 5, 5, 4, 3, 3,2,1,

%C 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,

%C 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.

%C In a row reversed version A(m, k) = a(m, m-(k+1)):

%C 1

%C 1,2

%C 1,2,3,3,

%C 1,2,3,3,4,5,5,4

%C 1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5

%C 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

%C each column k >= 0 is constant, namely A007306(k+1).

%C This row reversed version coincides with the array for A007305 (see the Jun 25 2014 comment there). (End)

%C 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

%H Alois P. Heinz, <a href="/A047679/b047679.txt">Table of n, a(n) for n = 0..10000</a>

%H N. J. A. Sloane, <a href="/stern_brocot.html">Stern-Brocot or Farey Tree</a>

%H <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>

%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>

%F a(n) = SternBrocotTreeDen(n) # n starting from 1.

%F From _Yosu Yurramendi_, Jul 02 2014: (Start)

%F For m >0 and 0 <= k < 2^(m-1), with a(0)=1, a(1)=2:

%F a(2^m+k-1) = a(2^(m-1)+k-1) + a((2^m-1)-k-1);

%F a(2^m+2^(m-1)+k-1) = a(2^(m-1)+k-1). (End)

%F a(2^m-2^q ) = q+1, q >= 0, m > q

%F a(2^m-2^q-1) = q+2, q >= 0, m > q+1. - _Yosu Yurramendi_, Jan 01 2015

%F a(2^(m+1)-1-k) = A007306(k+1), m >= 0, 0 <= k <= 2^m. - _Yosu Yurramendi_, May 20 2019

%F a(n) = A002487(1+A059893(n)), n > 0. - _Yosu Yurramendi_, Sep 29 2021

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

%e 1; 2,1; 3,3,2,1; 4,5,5,4,3,3,2,1; ....

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

%p 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].

%t CFruns[ n_Integer ] := Fold[ #2+1/#1&, Infinity, Reverse[ MapAt[ #+1&, Length/@Split[ IntegerDigits[ n, 2 ] ], {-1} ] ] ]

%t (* second program: *)

%t 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 *)

%o (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 */

%o (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

%o (R)

%o a <- 1

%o for(m in 1:6) for(k in 0:(2^(m-1)-1)) {

%o a[2^m+ k] = a[2^(m-1)+k] + a[2^m-k-1]

%o a[2^m+2^(m-1)+k] = a[2^(m-1)+k]

%o }

%o a

%o # _Yosu Yurramendi_, Dec 31 2014

%Y Cf. A007305, A007306, A054424, A152976.

%K nonn,easy,frac,nice,tabf,look

%O 0,2

%A _Wouter Meeussen_

%E Edited by _Wolfdieter Lang_, Mar 31 2015

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)