

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.


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 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)
n>1 occurs in this sequence phi(n) = A000010(n) times, as it occurs in A007306 (Franklin T. AdamsWatters's comment), that is the sequence obtained by adding numerator and denominator in the CalkinWilf 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) = (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).
From Yosu Yurramendi, Jun 27 2014: (Start)
Let it be 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


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, ...
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=N2^E)1)); CF=Vec(Ser(P)*(x1)); 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



