A336168 Garel's separator length for position n of the Thue-Morse sequence (A010060).

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

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), 81-113.

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 Thue-Morse 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