login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A071585 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. 17
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].

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

LINKS

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

Index entries for fraction trees

FORMULA

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

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^(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)

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

(PARI) {a(n)=local(N=4*n, E=#binary(N)-1, P=[E], CF); while(E>1, P=concat(P, E=#binary(N=N-2^E)-1)); CF=Vec(Ser(P)*(x-1)); CF[1]=0; contfracpnqn(CF)[2, 1]}

for(n=0, 256, print1(a(n), ", ")) \\ Paul D. Hanna, Feb 22 2013

(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

CROSSREFS

Cf. A071766.

Sequence in context: A280386 A204979 A243351 * A106500 A280315 A120245

Adjacent sequences:  A071582 A071583 A071584 * A071586 A071587 A071588

KEYWORD

easy,nice,nonn,frac

AUTHOR

Paul D. Hanna, Jun 01 2002

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 14:31 EDT 2019. Contains 328019 sequences. (Running on oeis4.)