A288003 - OEIS

%I #44 Apr 28 2021 16:27:30

%S 1,1,1,1,2,1,1,1,3,2,2,1,3,1,1,1,4,3,3,2,5,2,2,1,5,3,3,1,4,1,1,1,5,4,

%T 4,3,7,3,3,2,8,5,5,2,7,2,2,1,7,5,5,3,8,3,3,1,7,4,4,1,5,1,1,1,6,5,5,4,

%U 9,4,4,3,11,7,7,3,10,3,3,2,11,8,8,5,13,5

%N R-fusc, sequence r of the mutual diatomic recurrence pair: l(1)=0, r(1)=1, l(2n) = l(n), r(2n) = r(n), l(2n+1) = l(n)+r(n), r(2n+1) = l(n+1)+r(n+1), where l(n) = A288002(n).

%C Define a sequence chf(n) of Christoffel words over an alphabet {-,+}:

%C chf(1) = '-',

%C chf(2*n+0) = negate(chf(n)),

%C chf(2*n+1) = negate(concatenate(chf(n),chf(n+1))).

%C Each chf(n) word has the length fusc(n) = A002487(n) and splits uniquely into two parent Christoffel words - the left Christoffel word lef(n) of the length l-fusc(n) = A288002(n) and the right Christoffel word rig(n) of the length r-fusc(n) = a(n). See the example below.

%H Charles R Greathouse IV, <a href="/A288003/b288003.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = A002487(n) - A288002(n). [r-fusc(n) = fusc(n) - l-fusc(n).]

%F gcd(a(n),A288002(n)) = gcd(a(n),A002487(n)) = 1.

%e The odd bisection CHF(n) of the chf(n) sequence shifted rightwards by A288002(n) determines the longest overlap of the words CHF(n) and CHF(n+1). Note that the first overlapping letters differ for n == 2^k or equivalently when A288002(n)==0.

%e To construct the word CHF(n+1) from the word CHF(n): cut off the word negate(lef(n)) of length A288002(n) at the left side of CHF(n), add the word negate(rig(n)) of length a(n) at the right side of CHF(n) and negate the first letter of the new word iff A288002(n)==0.

%e n chf(n)  A070939(n) A002487(n) rig(n) a(n)       CHF(n)

%e                      fusc(n)           r-fusc(n)  bisection of chf(n)

%e 1  '-'     1          1         '+'     1        '-'

%e 2  '+'     2          1         '-'     1        '+-'

%e 3  '+-'    2          2         '-'     1        '--+'

%e 4  '-'     3          1         '+'     1         '-++'

%e 5  '--+'   3          3        '-+'     2         '+++-'

%e 6  '-+'    3          2         '+'     1          '++-+-'

%e 7  '-++'   3          3         '+'     1           '+-+--'

%e 8  '+'     4          1         '-'     1             '+---'

%e 9  '+++-'  4          4       '++-'     3             '----+'

%e 10 '++-'   4          3        '+-'     2              '---+--+'

%e 11 '++-+-' 4          5        '+-'     2               '--+--+-+'

%e 12 '+-'    4          2         '-'     1                  '--+-+-+'

%e 13 '+-+--' 4          5       '+--'     3                   '-+-+-++'

%e 14 '+--'   4          3         '-'     1                     '-+-++-++'

%e 15 '+---'  4          4         '-'     1                       '-++-+++'

%e 16 '-'     5          1         '+'     1                          '-++++'

%e 17 '----+' 5          5      '---+'     4                           '+++++-'

%o (Python)

%o def l(n): return 0 if n==1 else l(n//2) if n%2==0 else l((n - 1)//2) + r((n - 1)//2)

%o def r(n): return 1 if n==1 else r(n//2) if n%2==0 else l((n + 1)//2) + r((n + 1)//2)

%o print([r(n) for n in range(1, 151)]) # _Indranil Ghosh_, Jun 11 2017

%o (PARI) l(n)=if(n%2, if(n==1, 0, l(n\2) + a(n\2)), l(n/2))

%o a(n)=if(n%2, if(n==1, 1, l(n\2+1) + a(n\2+1)), a(n/2)) \\ _Charles R Greathouse IV_, Jun 11 2017

%Y Cf. A002487, A070939, A287729, A287730, A288002.

%K nonn

%O 1,5

%A _I. V. Serov_, Jun 10 2017