A287824 a(n) = A287730(n)*A001511(n).

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

Offset

1,2

Comments

For n > 0, define the sequence chf(n) of Christoffel words over an alphabet {-,+} by recursion with chf(1) = '-' and chf(2*n+0) = negate(chf(n)), chf(2*n+1) = negate(concatenate(chf(n),chf(n+1))).

The chf(n) word has length fusc(n) = A002487(n) and splits uniquely into two parent Christoffel words - the left Christoffel word lef(n) of length l-fusc(n) = A288002(n) and the right Christoffel word rig(n) of length r-fusc(n) = A288003(n).

For n > 0, define the lap(n) word as the chf(n) word taken to the power A001511(n), so that the factor-word chf(n) repeats lap(n) A001511(n) times.

Consider the odd bisection CHF(n) of the chf(n) sequence. Each CHF(n) word has length A007306(n). Then the sequence lap(n) is obtained by cutting off the word lef(n) of length A288002(n) at the left side of negate(CHF(n)) and negating the first letter of the new word iff lef(n) is empty, i.e., iff A288002(n)==0.

The length of the lap(n) word is A287896(n), the number of '-'-signs in the lap(n) word is A287823(n) and the number of '+'-signs in the lap(n) word is a(n).

There are exactly n words of length n in the sequence lap(n). These n words lap(j) are all different with 1 <= a(j) <= n for 1 <= j <= n.

a(n)/A287823(n) enumerates all fractions along the tree of fractions.

a(n)/A287896(n) enumerates all proper fractions along the tree of proper fractions.

See the Serov links and the example below.

Links

I. V. Serov, Table of n, a(n) for n = 1..8192

J. Berstel, A. Lauve, C. Reutenauer & F. Saliola, Combinatorics on Words: Christoffel Words and Repetitions in Words, 2008.

I. V. Serov, The tree of all fractions as sequence a(n)/A287823

I. V. Serov, The tree of all proper fractions as sequence a(n)/A287896

I. V. Serov, CHF Diatomic Algorithm Benchmark

Formula

a(n) = A287896(n) - A287823(n).

a(n) = (A287730(n-1) + A287730(n) + A287730(n+1))/2 - A154269(n).

gcd(a(n), A287896(n)) == gcd(a(n), A287823(n)) == A001511(n).

From Yosu Yurramendi, Apr 09 2019: (Start)

For m >= 0, m even, 0 <= k < 2^m, a(2^m+k) = A287896(k). A287896[0] = 0 is needed.

For m >= 0, m odd, 0 <= k < 2^m, a(2^m+k) = A287896(2^m-k).

(End)

Example

n  chf(n)  A070939(n) A001511(n) A002487(n) lef(n) CHF(n)     lap(n)   a(n)
                                 fusc(n)
1  '-'     1          1          1          ''     '-'        '-'      0
2  '+'     2          2          1          ''     '+-'       '++'     2
3  '+-'    2          2          2          '+'    '--+'      '+-'     1
4  '-'     3          1          1          ''     '-++'      '---'    0
5  '--+'   3          3          3          '-'    '+++-'     '--+'    1
6  '-+'    3          1          2          '-'    '++-+-'    '-+-+'   2
7  '-++'   3          1          3          '-+'   '+-+--'    '-++'    2
8  '+'     4          1          1           ''    '+---'     '++++'   4
9  '+++-'  4          4          4          '+'    '----+'    '+++-'   3
10 '++-'   4          1          3          '+'    '---+--+'  '++-++-' 4
11 '++-+-' 4          1          5          '++-'  '--+--+-+' '++-+-'  3
12 '+-'    4          1          2          '+'    '--+-+-+'  '+-+-+-' 3
13 '+-+--' 4          2          5          '+-'   '-+-+-++'  '+-+--'  2
14 '+--'   4          1          3          '+-'   '-+-++-++' '+--+--' 2
15 '+---'  4          1          4          '+--'  '-++-+++'  '+---'   1
16 '-'     5          1          1          ''     '-++++'    '-----'  0
17 '----+' 5          5          5          '-'    '+++++-'   '----+'  1   .

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 a001511(n): return bin(n)[2:][::-1].index("1") + 1
def a(n): return s(n)*a001511(n) # Indranil Ghosh, Jun 08 2017

Crossrefs

Cf. A001511, A287730, A287823, A002487, A070939, A287896, A154269.

Sequence in context: A035670 A058839 A275946 * A065364 A168318 A174203

Adjacent sequences: A287821 A287822 A287823 * A287825 A287826 A287827

Keyword

nonn,frac

Author

I. V. Serov, Jun 03 2017

Extensions

Name corrected by Indranil Ghosh, Jun 08 2017

Status

approved