|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
Table of n, a(n) for n=1..87.
Index entries for 2-automatic sequences.
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
Adjacent sequences: A335105 A335106 A335107 * A335109 A335110 A335111
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Jeffrey Shallit, May 23 2020
|
|
|
STATUS
|
approved
|
| |
|
|
