0,2

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

From Yosu Yurramendi, Jun 23 2014: (Start)

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

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)

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

a(n) = A086592(A059893(n)), a(A059893(n)) = A086592(n), n > 0. - Yosu Yurramendi, May 30 2017

Paul D. Hanna, Table of n, a(n) for n = 0..10000

a(2^k + 2^j + m) = (k-j)*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^(k-1)-1} a(2^k + m) = 3^k (k>0).

From Yosu Yurramendi, Jun 27 2014: (Start)

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)

a(n) = A059893(A086592(n)), n>0. - Yosu Yurramendi, Apr 09 2016

a(n) = A093873(n) + A093875(n), n > 0. - Yosu Yurramendi, Jul 22 2016

a(n) = A093873(2n) + A093873(2n+1), n > 0; a(n) = A093875(2n) = A093875(2n+1), n > 0. - Yosu Yurramendi, Jul 25 2016

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

a(n) = A007306(A059893(A233279(n))), n > 0. - Yosu Yurramendi, Aug 07 2021

a(n) = A007306(A059894(A006068(n))), n > 0. - Yosu Yurramendi, Sep 29 2021

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

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^(k-1)-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, ...

From Yosu Yurramendi, Jun 27 2014: (Start)

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)

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

(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

# Yosu Yurramendi, Jun 26 2014

(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

# Yosu Yurramendi, Jun 27 2014

Cf. A071766.

Sequence in context: A204979 A243351 A376635 * A328801 A106500 A280315

Adjacent sequences: A071582 A071583 A071584 * A071586 A071587 A071588

easy,nice,nonn,frac

Paul D. Hanna, Jun 01 2002

approved