A360104 Number of length-n blocks of the Thue-Morse infinite word (A010060), counted up to cyclic shift.

1, 2, 3, 2, 4, 4, 6, 8, 12, 8, 12, 16, 14, 18, 18, 18, 28, 20, 20, 28, 28, 28, 36, 36, 30, 40, 42, 40, 38, 48, 38, 40, 60, 40, 44, 56, 44, 56, 60, 56, 60, 64, 60, 64, 76, 64, 76, 80, 62, 82, 82, 74, 90, 78, 82, 90, 78, 86, 98, 90, 78, 102, 82, 82, 124, 84, 84

Offset

0,2

Comments

"Counted up to cyclic shift" means two blocks that are cyclic shifts of each other are treated as the same.

It is known that a(n) >= (4/3)n - 4 for n >= 0 and a(n) <= 2n-4 for n >= 3.

Links

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

C. Krawchuk and N. Rampersad, Cyclic complexity of some infinite words and generalizations, INTEGERS 18A (2018), #A12.

Jeffrey Shallit, Proof of a conjecture of Krawchuk and Rampersad, arXiv:2301.11473 [math.CO], 2023.

Jeffrey Shallit, Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence, Integers (2023) Vol. 23, #A44.

Formula

There is a linear representation of rank 10 to compute a(n), so it can be computed efficiently.

Example

For n = 5 the a(5) = 4 blocks counted are {00110, 01101, 10011, 10100}.

Crossrefs

Cf. A010060.

Sequence in context: A297117 A364464 A120680 * A356670 A071494 A326764

Adjacent sequences: A360101 A360102 A360103 * A360105 A360106 A360107

Keyword

nonn

Author

Jeffrey Shallit, Jan 26 2023

Status

approved