%I #106 Apr 24 2024 12:44:57
%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, ...
%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 (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