A245328 Denominators in recursive bijection from positive integers to positive rationals (the bijection is f(1) = 1, f(2n) = 1/(f(n)+1), f(2n+1) = f(n)+1).

1, 2, 1, 3, 2, 3, 1, 5, 3, 5, 2, 4, 3, 4, 1, 8, 5, 8, 3, 7, 5, 7, 2, 7, 4, 7, 3, 5, 4, 5, 1, 13, 8, 13, 5, 11, 8, 11, 3, 12, 7, 12, 5, 9, 7, 9, 2, 11, 7, 11, 4, 10, 7, 10, 3, 9, 5, 9, 4, 6, 5, 6, 1, 21, 13, 21, 8, 18, 13, 18, 5, 19, 11, 19, 8, 14, 11, 14, 3, 19, 12, 19, 7, 17, 12, 17, 5, 16, 9, 16, 7, 11, 9, 11, 2, 18, 11, 18, 7, 15

Offset: 1

Author

Yosu Yurramendi, Jul 18 2014

Keywords

• nonn
• frac

Comments

A245327(n)/a(n) enumerates all the reduced nonnegative rational numbers exactly once.

If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...

1,

2,1,

3,2, 3,1,

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

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

13,8,13,5,11,8,11,3,12,7,12,5,9,7,9,2,11,7,11,4,10,7,10,3,9,5,9,4,6,5,6,1,

then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence.

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

1,

2,1,

3,2,3,1,

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

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

13,8,13,5,11,8,11,3,12,7,12,5,9,7,9,2,11,7,11,4,10,7,10,3,9,5,9,4,6,5,6,1,

then each column is an arithmetic sequence. The differences of the arithmetic sequences, except the first on the right, give the sequence A093873 (Numerators in Kepler's tree of harmonic fractions) (a(2^(m+1)-1-k) - a(2^m-1-k) = A093873(k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).

If the sequence is considered by blocks of length 2^m, m = 0,1,2,..., the blocks of this sequence are permutations of terms of blocks from A002487 (Stern's diatomic series or Stern-Brocot sequence), and, more precisely, the reverses of blocks of A020651 ( a(2^m+k) = A020651(2^(m+1)-1-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).

Moreover, each block is the bit-reversed permutation of the corresponding block of A245326.

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..16383, rows 1-14, flattened.
• Index entries for fraction trees

Crossrefs

Cf. A002487, A020651, A093873, A245326, A245327, A273493.

Programs

Mathematica

f[n_] := Which[n == 1, 1, EvenQ@ n, 1/(f[n/2] + 1), True, f[(n - 1)/2] + 1]; Table[Denominator@ f@ k, {n, 7}, {k, 2^(n - 1), 2^n - 1}] // Flatten (* Michael De Vlieger, Mar 02 2017 *)

PARI

a(n) = my(A=0); forstep(i=logint(n, 2), 0, -1, if(bittest(n, i), A++, A=1/(A+1))); denominator(A) \\ Mikhail Kurkov, Mar 12 2023

R

N <- 25 # arbitrary
a <- c(1,2,1)
for(n in 1:N){
  a[4*n]   <- a[2*n] + a[2*n+1]
  a[4*n+1] <- a[2*n]
  a[4*n+2] <- a[2*n] + a[2*n+1]
  a[4*n+3] <-          a[2*n+1]
}
a

Formula

a(2n) = A245327(2n+1) , a(2n+1) = A245328(2n) , n=1,2,3,...

a((2*n+1)*2^m - 1) = A273493(n), n > 0, m >= 0. For n = 0 A273493(0) = 1 is needed. - Yosu Yurramendi, Mar 02 2017

a(n) = A002487(1+A284459(n)). - Yosu Yurramendi, Aug 23 2021