A335108 Number of periods of the length-n prefix of the Thue-Morse sequence (A010060).

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

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