login
A360104
Number of length-n blocks of the Thue-Morse infinite word (A010060), counted up to cyclic shift.
0
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
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.
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
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jan 26 2023
STATUS
approved