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

Author

Peter Luschny, Apr 06 2022

Keywords

• nonn

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", ...

Examples

			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"]
		

Links

• 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

Crossrefs

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

Programs

Maple

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