A071766 Denominator of the continued fraction expansion whose terms are the first-order differences of exponents in the binary representation of 4n, with the exponents of 2 being listed in descending order.

1, 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 5, 4, 5, 1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8, 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, 1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8, 6, 9, 10, 11, 9, 12, 11, 13

Offset: 0

Author

Paul D. Hanna, Jun 04 2002

Keywords

• easy
• nonn
• frac

Comments

If the terms (n>0) are written as an array:

1,

1, 2,

1, 2, 3, 3,

1, 2, 3, 3, 4, 5, 4, 5,

1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8,

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,

then the sum of the m-th row is 3^m (m = 0,1,2,3,...), each column is constant and the terms are from A071585 (a(2^m+k) = A071585(k), k = 0,1,2,...).

If the rows are written in a right-aligned fashion:

1,

1, 2,

1, 2, 3, 3,

1, 2, 3, 3, 4, 5, 4, 5,

1, 2, 3, 3, 4, 5, 4, 5, 5, 7, 7, 8, 5, 7, 7, 8,

..., 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^(m+2)+k) = a(2^(m+1)+k) + a(2^m+k), m = 0,1,2,..., k = 0,1,2,...,2^m-1 with a_k(1) = A071766(k) and a_k(2) = A086593(k) being the first two terms of each column sequence). - Yosu Yurramendi, Jun 23 2014

Examples

			a(37) = 5 as it is the denominator 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].
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, ...
		

Links

• Paul D. Hanna, Table of n, a(n) for n = 0..10000
• Index entries for fraction trees

Crossrefs

Cf. A071585, A086593.

Programs

Mathematica

{1}~Join~Table[Denominator@ FromContinuedFraction@ Append[Abs@ Differences@ #, Last@ #] &@ Log2[NumberExpand[4 n, 2] /. 0 -> Nothing], {n, 120}] (* Version 11, or *)
{1}~Join~Table[Denominator@ 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 <- 6 # arbitrary
a <- 1
for(m in 0:blocklevel) for(k in 0:(2^(m-1)-1)){
  a[2^(m+1)+k]             <- a[2^m+k]
  a[2^(m+1)+2^(m-1)+k]     <- a[2^m+2^(m-1)+k]
  a[2^(m+1)+2^m+k]         <- a[2^(m+1)+k]     +  a[2^(m+1)+2^(m-1)+k]
  a[2^(m+1)+2^m+2^(m-1)+k] <- a[2^(m+1)+2^m+k]
}
a
# Yosu Yurramendi, Jul 11 2014

Formula

a(n) = A071585(m), where m = n - floor(log_2(n));

a(0) = 1, a(2^k) = 1, a(2^k + 1) = 2.

a(2^k - 1) = Fibonacci(k+1) = A000045(k+1).

a(2^m+k) = A071585(k), m=0,1,2,..., k=0,1,2,...,2^m-1. - Yosu Yurramendi, Jun 23 2014

a(2^m-k) = F_k(m), k=0,1,2,..., m > log_2(k). F_k(m) is a Fibonacci sequence, where F_k(1) = a(2^(m_0(k))-1-k), F_k(2) = a(2^(m_0(k)+1)-1-k), m_0(k) = ceiling(log_2(k+1))+1 = A070941(k). - Yosu Yurramendi, Jun 23 2014

a(n) = A002487(A059893(A233279(n))) = A002487(1+A059893(A006068(n))), n > 0. - Yosu Yurramendi, Sep 29 2021