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.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 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 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 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 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

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