login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A336168 Garel's separator length for position n of the Thue-Morse 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), 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 05:55 EDT 2021. Contains 345080 sequences. (Running on oeis4.)