The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors 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. 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].
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
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
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
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
(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 * A328801 A106500 A280315
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 09:53 EDT 2024. Contains 372619 sequences. (Running on oeis4.)