A287731 Bisection of A287729.

1, 1, 2, 1, 1, 2, 3, 3, 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, 5, 7, 8, 7, 7, 8, 7, 5, 4, 5, 5, 4, 3, 3, 2, 1

Offset: 1

Author

I. V. Serov, Jun 01 2017

Keywords

• nonn
• frac

Comments

A287732(n)/a(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, The Stern-Brocot Tree as Sequence A287732/A287731
• N. J. A. Sloane, Stern-Brocot or Farey Tree
• Index entries for sequences related to Stern's sequences
• Index entries for fraction trees

Crossrefs

Cf. A002487, A007306, A287729, A287730, A287732.

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 c(2*n - 1) # Indranil Ghosh, Jun 08 2017

Formula

a(n) = A287729(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 = a(n) and s = A287732(n);