A245326 Denominators of an enumeration system of the reduced nonnegative rational numbers.

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

Offset

1,2

Comments

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

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

1,

2, 1,

3, 3, 2,1,

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

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

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

then the sum of the m-th row is 3^m (m = 0,1,2,), and each column k is a Fibonacci sequence. These Fibonacci sequences are equal to Fibonacci sequences from A...... except for the first terms of those sequences.

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

1,

2,1,

3,3,2,1,

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

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

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

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

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 the Stern-Brocot sequence), and, more precisely, the reverses of blocks of A071766 (a(2^m+k) = A071766(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 A245328.

Links

Table of n, a(n) for n=1..100.

Index entries for fraction trees

Formula

a(n) = A002487(1+A059893(A180200(n))) = A002487(A059893(A154435(n))). - Yosu Yurramendi, Sep 20 2021

Prog

(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+2^(m-1)+k]
  a[2^(m+1)+2^(m-1)+k]     <- a[2^(m+1)+k]
  a[2^(m+1)+2^m+k]         <- a[2^m+k]
  a[2^(m+1)+2^m+2^(m-1)+k] <- a[2^m+2^(m-1)+k]
}
a
(PARI) a(n) = my(A=1); for(i=0, logint(n, 2), if(bittest(2*n, i), A++, A=(A+1)/A)); denominator(A) \\ Mikhail Kurkov, Feb 20 2023

Crossrefs

Cf. A245325, A002487, A071585, A071766, A273494.

Cf. A002487, A059893, A154435.

Sequence in context: A324338 A047679 A179480 * A241534 A337137 A035050

Adjacent sequences: A245323 A245324 A245325 * A245327 A245328 A245329

Keyword

nonn,frac

Author

Yosu Yurramendi, Jul 18 2014

Status

approved