|
%I #111 Apr 24 2024 04:14:00
%S 1,2,3,3,4,5,4,5,5,7,7,8,5,7,7,8,6,9,10,11,9,12,11,13,6,9,10,11,9,12,
%T 11,13,7,11,13,14,13,17,15,18,11,16,17,19,14,19,18,21,7,11,13,14,13,
%U 17,15,18,11,16,17,19,14,19,18,21,8,13,16,17,17,22,19,23,16,23,24,27,19
%N Numerator of the continued fraction expansion whose terms are the first-order differences of exponents in the binary representation of 4*n, with the exponents of 2 being listed in descending order.
%C Thus a(n)/a(m) = d_1 + 1/(d_2 + 1/(d_3 + ... + 1/d_k)) where m = n - 2^floor(log_2(n)) + 1 and where d_j = b_j - b_(j+1) are the differences of the binary exponents b_j > b_(j+1) defined by: 4*n = 2^b_1 + 2^b_2 + 2^b_3 + ... 2^b_k.
%C All the rationals are uniquely represented by this sequence - compare Stern's diatomic sequence A002487.
%C This sequence lists the rationals >= 1 in order by the sum of the terms of their continued fraction expansions. For example, the numerators generated from partitions of 5 that do not end with 1 are listed together as 5, 7, 7, 8, 5, 7, 7, 8, since: 5/1 = [5]; 7/2 = [3;2]; 7/3 = [2;3]; 8/3 = [2;1,2]; 5/4 = [1;4]; 7/5 = [1;2,2]; 7/4 = [1;1,3]; 8/5 = [1;1,1,2].
%C From _Yosu Yurramendi_, Jun 23 2014: (Start)
%C If the terms (n>0) are written as an array:
%C 1,
%C 2,
%C 3, 3,
%C 4, 5, 4, 5,
%C 5, 7, 7, 8, 5, 7, 7, 8,
%C 6, 9,10,11, 9,12,11,13, 6, 9,10,11, 9,12,11,13,
%C 7,11,13,14,13,17,15,18,11,16,17,19,14,19,18,21,7,11,13,14,13,17,15,18,11, ...
%C then the sum of the k-th row is 2*3^(k-2) for k>1, each column is an arithmetic progression. The differences of the arithmetic sequences give the sequence A071585 itself: a(2^(p+1)+k) - a(2^p+k) = a(k). A002487 and A007306 also have these properties. The first terms of columns, excluding a(0), give A086593.
%C If the rows (n>0) are written on right:
%C 1;
%C 2;
%C 3, 3;
%C 4, 5, 4, 5;
%C 5, 7, 7, 8, 5, 7, 7, 8;
%C 6, 9, 10, 11, 9, 12, 11, 13, 6, 9, 10, 11, 9, 12, 11, 13;
%C then each column is a Fibonacci sequence: a(2^(p+2)+k) = a(2^(p+1)+k) + a(2^p+k). The first terms of columns, excluding a(0), give A086593. (End)
%C n>1 occurs in this sequence phi(n) = A000010(n) times, as it occurs in A007306 (_Franklin T. Adams-Watters_'s comment), that is the sequence obtained by adding numerator and denominator in the Calkin-Wilf enumeration system of positive rationals. A229742(n)/A071766(n) is also an enumeration system of all positive rationals (HCS system), and in each level m >= 0 (ranks between 2^m and 2^(m+1)-1) rationals are the same in both systems. Thus a(n) (A229742(n)+A071766(n)) has the same terms in each level as A007306. The same property occurs in all numerator+denominator sequences of enumeration systems of positive rationals, as, for example, A007306 (A007305+A047679), A086592 (A020650+A020651), and A268087 (A162909+A162910). - _Yosu Yurramendi_, Apr 06 2016
%C a(n) = A086592(A059893(n)), a(A059893(n)) = A086592(n), n > 0. - _Yosu Yurramendi_, May 30 2017
%H Paul D. Hanna, <a href="/A071585/b071585.txt">Table of n, a(n) for n = 0..10000</a>
%H <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%F a(2^k + 2^j + m) = (k-j)*a(2^j + m) + a(m) when 2^k > 2^j > m >= 0.
%F a(0) = 1, a(2^k) = k + 2,
%F a(2^k + 1) = 2*k + 1 (k>0),
%F a(2^k + 2) = 3*k - 2 (k>1),
%F a(2^k + 3) = 3*k - 1 (k>1),
%F a(2^k + 4) = 4*k - 7 (k>2).
%F a(2^k - 1) = Fibonacci(k+2) = A000045(k+2).
%F Sum_{m=0..2^(k-1)-1} a(2^k + m) = 3^k (k>0).
%F From _Yosu Yurramendi_, Jun 27 2014: (Start)
%F Write n = k + 2^(m+1), k = 0,1,2,...,2^(m+1)-1, m = 0,1,2,...
%F if 0 <= k < 2^m, a(k + 2^(m+1)) = a(k) + a(k + 2^m).
%F if 2^m <= k < 2^(m+1), a(k + 2^(m+1)) = a(k) + a(k - 2^m).
%F with a(0)=1, a(1)=2. (End)
%F a(n) = A059893(A086592(n)), n>0. - _Yosu Yurramendi_, Apr 09 2016
%F a(n) = A093873(n) + A093875(n), n > 0. - _Yosu Yurramendi_, Jul 22 2016
%F a(n) = A093873(2n) + A093873(2n+1), n > 0; a(n) = A093875(2n) = A093875(2n+1), n > 0. - _Yosu Yurramendi_, Jul 25 2016
%F a(n) = sqrt(A071766(2^(m+1)+n)*A229742(2^(m+1)+n) - A071766(2^m+n)*A229742(2^m+n)), for n > 0, where m = floor(log_2(n)+1). - _Yosu Yurramendi_, Jun 10 2019
%F a(n) = A007306(A059893(A233279(n))), n > 0. - _Yosu Yurramendi_, Aug 07 2021
%F a(n) = A007306(A059894(A006068(n))), n > 0. - _Yosu Yurramendi_, Sep 29 2021
%F Conjecture: a(n) = a(floor(n/2)) + Sum_{k=1..A000120(n)} a(b(n, k))*(-1)^(k-1) for n > 0 with a(0) = 1 where b(n, k) = A025480(b(n, k-1) - 1) for n > 0, k > 0 with b(n, 0) = n. - _Mikhail Kurkov_, Feb 20 2023
%e a(37)=17 as it is the numerator of 17/5 = 3 + 1/(2 + 1/2), which is a continued fraction that can be derived from the binary expansion of 4*37 = 2^7 + 2^4 + 2^2; the binary exponents are {7, 4, 2}, thus the differences of these exponents are {3, 2, 2}; giving the continued fraction expansion of 17/5=[3,2,2].
%e Illustration of Sum_{m=0..2^(k-1)-1} a(2^k + m) = 3^k:
%e k=2: 3^2 = a(2^2) + a(2^2 + 1) = 4 + 5;
%e k=3: 3^3 = a(2^3) + a(2^3 + 1) + a(2^3 + 2) + a(2^3 + 3) = 5 + 7 + 7 + 8;
%e k=4: 3^4 = a(2^4) + a(2^4+1) + a(2^4+2) + a(2^4+3) + a(2^4+4) + a(2^4+5) + a(2^4+6) + a(2^4+7) = 6 + 9 + 10 + 11 + 9 + 12 + 11 + 13.
%e 1, 2, 3, 3/2, 4, 5/2, 4/3, 5/3, 5, 7/2, 7/3, 8/3, 5/4, 7/5, 7/4, 8/5, 6, ...
%e From _Yosu Yurramendi_, Jun 27 2014: (Start)
%e a(0) = = 1;
%e a(1) = a(0) + a(0) = 2;
%e a(2) = a(0) + a(1) = 3;
%e a(3) = a(1) + a(0) = 3;
%e a(4) = a(0) + a(2) = 4;
%e a(5) = a(1) + a(3) = 5;
%e a(6) = a(2) + a(0) = 4;
%e a(7) = a(3) + a(1) = 5;
%e a(8) = a(0) + a(4) = 5;
%e a(9) = a(1) + a(5) = 7;
%e a(10) = a(2) + a(6) = 7;
%e a(11) = a(3) + a(7) = 8;
%e a(12) = a(4) + a(0) = 5;
%e a(13) = a(5) + a(1) = 7;
%e a(14) = a(6) + a(2) = 7;
%e a(15) = a(7) + a(3) = 8. (End)
%t ncf[n_]:=Module[{br=Reverse[Flatten[Position[Reverse[IntegerDigits[4 n,2]],1]-1]]}, Numerator[FromContinuedFraction[Flatten[Join[{Abs[ Differences[ br]],Last[br]}]]]]]; Join[{1},Array[ncf,80]] (* _Harvey P. Dale_, Jul 01 2012 *)
%t {1}~Join~Table[Numerator@ FromContinuedFraction@ Append[Abs@ Differences@ #, Last@ #] &@ Log2[NumberExpand[4 n, 2] /. 0 -> Nothing], {n, 120}] (* Version 11, or *)
%t {1}~Join~Table[Numerator@ FromContinuedFraction@ Append[Abs@ Differences@ #, Last@ #] &@ Log2@ DeleteCases[# Reverse[2^Range[0, Length@ # - 1]] &@ IntegerDigits[4 n, 2], k_ /; k == 0], {n, 120}] (* _Michael De Vlieger_, Aug 15 2016 *)
%o (R)
%o blocklevel <- 7 # arbitrary
%o a <- c(1,2)
%o for(k in 1:blocklevel)
%o a <- c(a, a + c(a[((length(a)/2)+1):length(a)],a[1:(length(a)/2)]))
%o a
%o # _Yosu Yurramendi_, Jun 26 2014
%o (R)
%o blocklevel <- 7 # arbitrary
%o a <- c(1,2)
%o for(p in 0:blocklevel)
%o for(k in 1:2^(p+1)){
%o if (k <= 2^p) a[k + 2^(p+1)] = a[k] + a[k + 2^p]
%o else a[k + 2^(p+1)] = a[k] + a[k - 2^p]
%o }
%o a
%o # _Yosu Yurramendi_, Jun 27 2014
%Y Cf. A071766.
%K easy,nice,nonn,frac,changed
%O 0,2
%A _Paul D. Hanna_, Jun 01 2002
|
