A352746 a(n) is the number of Lyndon factors of the Thue-Morse string of length n.

0, 1, 1, 1, 2, 2, 3, 4, 3, 3, 4, 5, 4, 5, 4, 4, 5, 4, 5, 6, 5, 6, 5, 5, 6, 7, 6, 5, 6, 5, 6, 7, 6, 5, 6, 7, 6, 7, 6, 6, 7, 8, 7, 6, 7, 6, 7, 8, 7, 8, 7, 7, 8, 6, 7, 8, 7, 6, 7, 8, 7, 8, 7, 7, 8, 6, 7, 8, 7, 8, 7, 7, 8, 9, 8, 7, 8, 7, 8, 9, 8, 9, 8, 8, 9, 7, 8

Offset

0,5

Comments

The Thue-Morse string of length n is the length-n prefix of the infinite Thue-Morse string. The sequence starts: "", "0", "01", "011", "0110", "01101", "011010", ...

Links

Table of n, a(n) for n=0..86.

Augustin Ido and Guy Melançon, Lyndon factorization of the Thue-Morse word and its relatives, Discret. Math. Theor. Comput. Sci. 1997.

Wikipedia, Lyndon word

Example

The Lyndon factorization of the Thue-Morse strings of length n = 0..9.
[0] []
[1] ["0"]
[2] ["01"]
[3] ["011"]
[4] ["011", "0"]
[5] ["011", "01"]
[6] ["011", "01", "0"]
[7] ["011", "01", "0", "0"]
[8] ["011", "01", "001"]
[9] ["011", "01", "0011"]

Maple

with(StringTools): A352746 := n -> nops(LyndonFactors(ThueMorse(n))):
seq(A352746(n), n = 0..12);

Crossrefs

Cf. A000045, A014707, A074650, A211100, A352745.

Sequence in context: A350238 A374994 A374992 * A330416 A359043 A054703

Adjacent sequences: A352743 A352744 A352745 * A352747 A352748 A352749

Keyword

nonn

Author

Peter Luschny, Apr 06 2022

Status

approved