OFFSET
0
COMMENTS
Notation:
Let ~ denote negation of a word over an alphabet A = {-,+}.
Let <worda,wordb> denote concatenation of two words.
Let # denote conversion of an integer sequence defined over the alphabet A into the binary domain B = {0,1}.
Let the operation |(word,condition) negate the first letter of the word if the condition is true.
Let the operation (word,condition)| negate the last letter of the word if the condition is true.
Construction:
For n > 0, define the sequence chf(n) of Christoffel words over an alphabet {'-','+'} by recursion with chf(1) = '-' and chf(2*n+0) = ~chf(n), chf(2*n+1) = ~<chf(n),chf(n+1)>.
The chf(n) word has length z(n) = A002487(n) and splits uniquely into two parent Christoffel words: the left Christoffel word lef(n) of length l(n) == A288002(n) and the right Christoffel word rig(n) of length r(n) == A288003(n). Note that a one-letter word 'a' splits by definition into '' at the left and ~'a' at the right side.
The chf(n) word also splits uniquely into parent palindromes:
The word ala(n) = chf(n)[1..r(n)] == rig(n)| is the left palindromic parent of chf(n) with length r(n).
The word ara(n) = chf(n)[r(n)+1..z(n)] == |lef(n) is the right palindromic parent of chf(n) with length l(n).
Consider the odd bisection CHF(n) of the chf(n) sequence. The CHF(n) word has length Z(n) = A007306(n) and splits uniquely into two parent Christoffel words: the left LEF(n) of length L(n) == A002487(n-1) and the right RIG(n) of length R(n) == A002487(n). The word RIG(n) == ~chf(n).
The CHF(n) word splits uniquely into parent palindromes as well:
The word ALA(n) = CHF(n)[1..R(n)] == RIG(n)| is the left palindromic parent of CHF(n) with length R(n).
The word ARA(n) = CHF(n)[R(n)+1..Z(n)] == |LEF(n) is the right palindromic parent of CHF(n) with length L(n).
For n > 0, define the lap(n) word to be the chf(n) word taken to the power A001511(n), so that the factor-word chf(n) repeats in lap(n) A001511(n) times.
The CHF(n+1) word shifted rightwards relative to the CHF(n) word by A288002(n) letters of lef(n) determines the longest overlap LAP(n) of the words CHF(n) and CHF(n+1). Note that the first overlapping letters differ iff n == 2^k: CHF(n)[1] == |(CHF(n+1)[1],A288002(n)==0).
For n > 0, the sequence LAP(n) == ~lap(n) is obtained by cutting off the word ~lef(n) at the left side of CHF(n) and negating the first letter of the new word iff lef(n) is empty: LAP(n) = |(CHF(n)[l+1:Z],A288002(n)==0).
For n > 0, the word cut(n) is defined by cut(n) = |(~lef(n),L(n)==1). For n = 0, cut(n) = ''.
For n > 0, the word add(n) is defined by add(n) = ~rig(n). For n = 0, add(0) = '+'.
For n > 0, CHF(n+1) = <LAP(n),add(n)>.
For n = 0, CHF(n+1) = <|(add(n),n==0)> = LAP(n).
Let i(1) = 1 and for n > 1, let i(n) == A289341(n) be the partial sum of l(1..n-1) + 1.
Let j(1) = 1 and for n > 1, let j(n) == A289342(n) be the partial sum of r(1..n-1) + 1.
For (n > 0 and 1 <= k <= r(n)), construct C_H_F(j(n)+k) = add(n)[k].
For n >= 0, a(n) = #C_H_F(n).
See the example below.
REFERENCES
E. B. Christoffel. Observatio arithmetica. Math. ann., 6:145-152, 1875.
LINKS
FORMULA
For n > 0:
{
Let the current block of the sequence be denoted as
H = a(i(n) .. j(n)).
H = a(i(n) .. i(n)+Z(n)-1).
Then:
#CHF(n) = |( a(i(n) .. i(n)+Z(n)-1 ), ispalindrom(H)) ;
#LEF(n) = |( a(i(n) .. i(n)+L(n)-1 ), ispalindrom(H)) ;
#RIG(n) = ( a(i(n)+L(n) .. i(n)+Z(n)-1 ) ;
#chf(n) = (-a(i(n)+L(n) .. i(n)+Z(n)-1 ) ;
#lef(n) = |(-a(i(n)+L(n)+r(n).. i+Z(n)-1 ), 1) ;
#rig(n) = (-a(i(n)+L(n) .. i(n)+L(n)+r(n)-1), 1)|;
#lap(n) = |(-a(i(n)+l(n) .. i(n)+Z(n)-1 ),n > 1 & l(n)==0 ) ;
#LAP(n) = |( a(i(n)+l(n) .. i(n)+Z(n)-1 ),n > 1 & l(n)==0 ) ;
#cut(n) = |( a(i(n)+L(n) .. i(n)+L(n)+l(n)-1), ispalindrom(H)) ;
#add(n) = |( a(i(n)+L(n)+l(n).. i+Z(n)-1 ), l(n)==0 ) ;
#CHF(n+1) = <LAP(n),add(n)>.
Here:
Z(n) = A007306(n ) = length(CHF(n));
L(n) = A002487(n-1) = length(LEF(n));
R(n) = A002487(n ) = length(RIG(n));
z(n) = A002487(n ) = length(chf(n));
l(n) = A288002(n ) = length(lef(n)) = length(cut(n));
r(n) = A288003(n ) = length(rig(n)) = length(add(n));
o(n) = A287896(n ) = length(lap(n)) = length(LAP(n));
i(n) = A289341(n);
j(n) = A289342(n).
}
EXAMPLE
Example I.
n chf(n) lef(n) LEF(n) LAP(n) cut(n) add(n) CHF(n)
-1 '-' '' '' '+' '' '-' '-'
------------------------------------------------------
0 '+' '' '' '-' '' '+' '+'
------------------------------------------------------
1 '-' '' '' '+' '' '-' '-'
2 '+' '' '+' '--' '' '+' '+-'
3 '+-' '-' '-' '-+' '+' '+' '--+'
4 '- ' '' '-+' '+++' '' '-' '-++'
5 '--+' '+' '+' '++-' '-' '+-' '+++-'
6 '-+' '+' '++-' '+-+-' '+' '-' .'++-+-'
7 '-++' '+-' '+-' '+--' '+-' '-' . '+-+--'
8 '+' '' '+--' '----' '' '+' . '+---'
9 '+++-' '-' '-' '---+' '+' '--+' . '----+'
10 '++-' '-' '---+' '--+--+' '-' '-+' . '---+--+'
11 '++-+-' '--+' '--+' '--+-+' '--+' '-+' . '--+--+-+'
12 '+-' '-' '--+-+' '-+-+-+' '-' '+' . '--+-+-+'
13 '+-+--' '-+' '-+' '-+-++' '-+' '-++' . '-+-+-++'
14 '+--' '-+' '-+-++' '-++-++' '-+' '+' . '-+-++-++'
15 '+---' '-++' '-++' '-+++' '-++' '+' . '-++-+++'
16 '-' '' '-+++' '+++++' '' '-' . '-++++'
17 '----+' '+' '+' '++++-' '-' '+++-' . '+++++-'
The Chain Hereditary Form of n = 17 is C_H_F(17)='+-++-+---+--+-+-++-++++-'
a(0..17) = #C_H_F(17)='+-++-+---+--+-+-++-++++-'
= [1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,1,1,0,1,1,1,1,0].
Example II.
0123456789012345678901234567890123456789012345
'+-++-+---+--+-+-++-++++-+++-++-++-+-++-+-+-+--'
CHF(22)='++-++-+-++-+-'
ALA(22)='++-++'
ARA(22)='-+-++-+-'
LEF(22)='++-++-+-'
RIG(22)='++-+-'
chf(22)='--+-+'
ala(22)='--'
ara(22)='+-+'
lef(22)='--+'
rig(22)='-+'
cut(22)='++-'
LAP(22)='++-+-++-+-'
add(22)='+-'
CHF(23)='++-+-++-+-+-'
ALA(23)='++-+-++'
ARA(23)='-+-+-'
LEF(23)='++-+-'
RIG(23)='++-+-+-'
chf(23)='--+-+-+'
ala(23)='--'
ara(23)='+-+-+'
lef(23)='--+-+'
rig(23)='-+'
cut(23)='++-+-'
LAP(23)='++-+-+-'
add(23)='+-'
CHF(24)='++-+-+-+-'
ALA(24)='++'
ARA(24)='-+-+-+-'
LEF(24)='++-+-+-'
RIG(24)='+-'.
Example III.
n C_H_F(n)
0 '+'
1 '+-'
2 '+-+'
3 '+-++'
4 '+-++-'
5 '+-++-+'
6 '+-++-+--'
7 '+-++-+---'
8 '+-++-+---+'
9 '+-++-+---+-'.
CROSSREFS
KEYWORD
nonn
AUTHOR
I. V. Serov, Jun 30 2017
STATUS
approved