A287732 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

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

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);

PROG

(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

CROSSREFS

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

Sequence in context: A123548 A131838 A274885 * A334223 A171414 A270921

Adjacent sequences: A287729 A287730 A287731 * A287733 A287734 A287735

KEYWORD

nonn,frac

AUTHOR

I. V. Serov, Jun 01 2017

STATUS

approved