

A071585


Numerator of the continued fraction expansion whose terms are the firstorder differences of exponents in the binary representation of 4*n, with the exponents of 2 being listed in descending order.


19



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, 11, 13, 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, 16, 17, 19, 14, 19, 18, 21, 8, 13, 16, 17, 17, 22, 19, 23, 16, 23, 24, 27, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

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.
All the rationals are uniquely represented by this sequence  compare Stern's diatomic sequence A002487.
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].
If the terms (n>0) are written as an array:
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,11,13,
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, ...
then the sum of the kth row is 2*3^(k2) 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.
If the rows (n>0) are written on right:
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, 11, 13;
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)


LINKS



FORMULA

a(2^k + 2^j + m) = (kj)*a(2^j + m) + a(m) when 2^k > 2^j > m >= 0.
a(0) = 1, a(2^k) = k + 2,
a(2^k + 1) = 2*k + 1 (k>0),
a(2^k + 2) = 3*k  2 (k>1),
a(2^k + 3) = 3*k  1 (k>1),
a(2^k + 4) = 4*k  7 (k>2).
a(2^k  1) = Fibonacci(k+2) = A000045(k+2).
Sum_{m=0..2^(k1)1} a(2^k + m) = 3^k (k>0).
Write n = k + 2^(m+1), k = 0,1,2,...,2^(m+1)1, m = 0,1,2,...
if 0 <= k < 2^m, a(k + 2^(m+1)) = a(k) + a(k + 2^m).
if 2^m <= k < 2^(m+1), a(k + 2^(m+1)) = a(k) + a(k  2^m).
with a(0)=1, a(1)=2. (End)
Conjecture: a(n) = a(floor(n/2)) + Sum_{k=1..A000120(n)} a(b(n, k))*(1)^(k1) for n > 0 with a(0) = 1 where b(n, k) = A025480(b(n, k1)  1) for n > 0, k > 0 with b(n, 0) = n.  Mikhail Kurkov, Feb 20 2023


EXAMPLE

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].
Illustration of Sum_{m=0..2^(k1)1} a(2^k + m) = 3^k:
k=2: 3^2 = a(2^2) + a(2^2 + 1) = 4 + 5;
k=3: 3^3 = a(2^3) + a(2^3 + 1) + a(2^3 + 2) + a(2^3 + 3) = 5 + 7 + 7 + 8;
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.
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, ...
a(0) = = 1;
a(1) = a(0) + a(0) = 2;
a(2) = a(0) + a(1) = 3;
a(3) = a(1) + a(0) = 3;
a(4) = a(0) + a(2) = 4;
a(5) = a(1) + a(3) = 5;
a(6) = a(2) + a(0) = 4;
a(7) = a(3) + a(1) = 5;
a(8) = a(0) + a(4) = 5;
a(9) = a(1) + a(5) = 7;
a(10) = a(2) + a(6) = 7;
a(11) = a(3) + a(7) = 8;
a(12) = a(4) + a(0) = 5;
a(13) = a(5) + a(1) = 7;
a(14) = a(6) + a(2) = 7;
a(15) = a(7) + a(3) = 8. (End)


MATHEMATICA

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 *)
{1}~Join~Table[Numerator@ FromContinuedFraction@ Append[Abs@ Differences@ #, Last@ #] &@ Log2[NumberExpand[4 n, 2] /. 0 > Nothing], {n, 120}] (* Version 11, or *)
{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 *)


PROG

(R)
blocklevel < 7 # arbitrary
a < c(1, 2)
for(k in 1:blocklevel)
a < c(a, a + c(a[((length(a)/2)+1):length(a)], a[1:(length(a)/2)]))
a
(R)
blocklevel < 7 # arbitrary
a < c(1, 2)
for(p in 0:blocklevel)
for(k in 1:2^(p+1)){
if (k <= 2^p) a[k + 2^(p+1)] = a[k] + a[k + 2^p]
else a[k + 2^(p+1)] = a[k] + a[k  2^p]
}
a


CROSSREFS



KEYWORD

easy,nice,nonn,frac


AUTHOR



STATUS

approved



