

A335108


Number of periods of the lengthn prefix of the ThueMorse 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 lengthn word x is an integer p, 1 <= p <= n, such that x[i]=x[i+p] for 1 <= i <= np.
This is a 2regular 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) + 1t(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 2automatic 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 ThueMorse sequence, are p = 1, 4, and 10.


CROSSREFS

Cf. A010060.
Sequence in context: A024708 A096917 A336664 * A320011 A068049 A297850
Adjacent sequences: A335105 A335106 A335107 * A335109 A335110 A335111


KEYWORD

nonn


AUTHOR

Jeffrey Shallit, May 23 2020


STATUS

approved



