

A336168


Garel's separator length for position n of the ThueMorse sequence (A010060).


0



1, 1, 2, 3, 3, 2, 5, 4, 5, 4, 4, 4, 9, 8, 7, 6, 9, 8, 7, 6, 7, 6, 7, 6, 17, 16, 15, 14, 13, 12, 11, 10, 17, 16, 15, 14, 13, 12, 11, 10, 13, 12, 11, 10, 13, 12, 11, 10, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 33, 32, 31, 30, 29, 28, 27
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The separator length at position n is the length of the shortest block beginning at that position that never appeared earlier in the sequence.


LINKS

Table of n, a(n) for n=0..70.
E. Garel, Séparateurs dans les mots infinis engendrés par morphismes, Theor. Comput. Sci. 180 (1997), 81113.


FORMULA

a(4*n+3) = 2*a(2*n)  2*a(2*n+1)  2*a(4*n) + a(4*n+1) + 2*a(4*n+2).
a(8*n) = 2*a(2*n) + 3*a(4*n).
a(8*n+1) = 2*a(2*n) + 2*a(4*n) + a(4*n+1).
a(8*n+2) = 2*a(n)  4*a(2*n) + a(2*n+1) + a(4*n) + 2*a(4*n+1).
a(8*n+4) = 2*a(2*n) + a(4*n) + 2*a(4*n+2).
a(8*n+5) = 4*a(2*n) + 2*a(4*n) + 2*a(4*n+2).
a(8*n+6) = 2*a(2*n)  4*a(2*n+1)  3*a(4*n) + 2*a(4*n+1) + 4*a(4*n+2).


EXAMPLE

The first 10 symbols of ThueMorse are 011010011001. We index it starting with index 0. Then a(6) = 5, because a(6..9) = 0110 already appears, while a(6..10) = 01100 does not.


CROSSREFS

Cf. A010060.
Sequence in context: A131899 A095174 A131307 * A091813 A238114 A291300
Adjacent sequences: A336165 A336166 A336167 * A336169 A336170 A336171


KEYWORD

nonn


AUTHOR

Jeffrey Shallit, Jul 10 2020


STATUS

approved



