A336173 The Mignosi-Restivo repetition length for the Thue-Morse sequence (A010060) at position n.

1, 3, 1, 6, 2, 12, 1, 12, 1, 24, 1, 24, 2, 24, 1, 24, 2, 48, 1, 48, 2, 48, 1, 48, 1, 48, 1, 48, 2, 48, 1, 48, 1, 96, 1, 96, 2, 96, 1, 96, 1, 96, 1, 96, 2, 96, 1, 96, 2, 96, 1, 96, 2, 96, 1, 96, 1, 96, 1, 96, 2, 96, 1, 96, 2, 192, 1, 192, 2, 192, 1, 192, 1, 192

Offset

0,2

Comments

The repetition length at position n of a sequence x = x[0] x[1] x[2]... is the smallest integer i such that either x[0..n-1] is a suffix of x[n..n+i-1], or x[n..n+i-1] is a suffix of x[0..n-1].

Links

Table of n, a(n) for n=0..73.

F. Mignosi and A. Restivo, Characteristic Sturmian words are extremal for the Critical Factorization Theorem 454(2012) 199-205.

Formula

a(4n+2) = (3a(2n) + 2a(2n+1) + 3a(4n) - a(4n+1))/9;

a(4n+3) = a(2n+1);

a(8n) = a(2n);

a(8n+1) = -2a(2n+1) + 3a(4n+1);

a(8n+4) = (6a(2n) + 4a(2n+1) + 6a(4n) - 2a(4n+1))/9;

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

Example

For n=3 we have a(n) = 6, because the first few symbols of the Thue-Morse sequence is 011010011, and 010011 has suffix 011.

Crossrefs

Cf. A010060.

Sequence in context: A105358 A240691 A322387 * A072361 A341219 A145366

Adjacent sequences: A336170 A336171 A336172 * A336174 A336175 A336176

Keyword

nonn

Author

Jeffrey Shallit, Jul 10 2020

Status

approved