A287732 Bisection of A287730.

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

Offset: 1

Author

I. V. Serov, Jun 01 2017

Keywords

• nonn
• frac

Comments

a(n)/A287731(n) enumerates all reduced fractions along the Stern-Brocot Tree. See the Serov link below.

Links

• I. V. Serov, Table of n, a(n) for n = 1..8192
• I. V. Serov, OEIS: The Stern-Brocot Tree as Sequence A287732/A287731
• N. J. A. Sloane, Stern-Brocot or Farey Tree
• Index entries for fraction trees
• Index entries for sequences related to Stern's sequences

Crossrefs

Cf. A002487, A007306, A287729, A287730, A287731.

Programs

Python

def c(n): return 1 if n==1 else s(n/2) if n%2==0 else s((n - 1)/2) + s((n + 1)/2)
def s(n): return 0 if n==1 else c(n/2) if n%2==0 else c((n - 1)/2) + c((n + 1)/2)
def a(n): return s(2*n - 1) # Indranil Ghosh, Jun 08 2017

Formula

a(n) = A287730(2*n-1), n > 0.

a(n) = A287730(n-1) + A287730(n), n > 0.

a(n) = A007306(n) - A287732(n).

Consider for n > 1 the binary expansion b(1:t) of n-1 without the leading 1.

Recurse: c=s=1; for j=1:t {if b(t-j+1) == mod(t,2) s = s+c; else c = c+s;}

Then: c = A287731(n) and s = a(n);