login
A335108
Number of periods of the length-n prefix of the Thue-Morse sequence (A010060).
0
1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 3, 3, 3, 4, 3, 3, 3, 4, 4, 4, 4, 4, 2, 2, 2, 3, 3, 3, 3
OFFSET
1,4
COMMENTS
A period of a length-n word x is an integer p, 1 <= p <= n, such that x[i]=x[i+p] for 1 <= i <= n-p.
This is a 2-regular sequence. It satisfies the identity
a(4n) = a(n)+1 for n > 0, and the identities
a(4n+3) = a(4n+1)
a(8n+1) = a(2n+1) + t(n)
a(8n+2) = a(4n+1) + t(n)
a(8n+6) = a(4n+1) + 1-t(n)
a(16n+5) = a(2n+1) + 1
a(16n+13) = a(4n+1) + 1
for n >= 0. Here t(n) = A010060(n).
LINKS
D. Gabric, N. Rampersad, and J. Shallit, An inequality for the number of periods in a word, arxiv preprint arXiv:2005.11718 [cs.DM], May 24 2020.
EXAMPLE
For n = 10, the a(10) = 3 periods of 0110100110, the first 10 symbols of the Thue-Morse sequence, are p = 1, 4, and 10.
CROSSREFS
Cf. A010060.
Sequence in context: A024708 A096917 A336664 * A359238 A320011 A068049
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 23 2020
STATUS
approved