A352746 - OEIS

%I #8 Apr 07 2022 00:36:07

%S 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,

%T 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,

%U 7,8,7,7,8,9,8,7,8,7,8,9,8,9,8,8,9,7,8

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

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

%H Augustin Ido and Guy Melançon, <a href="http://dml.mathdoc.fr/item/01375570/">Lyndon factorization of the Thue-Morse word and its relatives</a>, Discret. Math. Theor. Comput. Sci. 1997.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lyndon_word">Lyndon word</a>

%e The Lyndon factorization of the Thue-Morse strings of length n = 0..9.

%e [0] []

%e [1] ["0"]

%e [2] ["01"]

%e [3] ["011"]

%e [4] ["011", "0"]

%e [5] ["011", "01"]

%e [6] ["011", "01", "0"]

%e [7] ["011", "01", "0", "0"]

%e [8] ["011", "01", "001"]

%e [9] ["011", "01", "0011"]

%p with(StringTools): A352746 := n -> nops(LyndonFactors(ThueMorse(n))):

%p seq(A352746(n), n = 0..12);

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

%K nonn

%O 0,5

%A _Peter Luschny_, Apr 06 2022