A352745 a(n) is the number of Lyndon factors of the Fibonacci string of length n.

1, 1, 1, 2, 2, 3, 4, 4, 6, 5, 8, 6, 10, 7, 12, 8, 14, 9, 16, 10, 18, 11, 20, 12, 22, 13, 24, 14, 26, 15, 28, 16, 30, 17, 32, 18, 34, 19, 36, 20, 38, 21, 40, 22, 42, 23, 44

Offset: 0

Author

Peter Luschny, Apr 06 2022

Keywords

• nonn
• more

Comments

The Fibonacci string of length n is defined Fibonacci(n) = cat(Fibonacci(n - 1), Fibonacci(n - 2)) for 1 < n and the initial conditions Fibonacci(0) = "1" and Fibonacci(1) = "0", where 'cat' is the operation of concatenating strings. The length of Fibonacci(n) is A352744(1, n). The sequence starts: "1", "0", "01", "010", "01001", "01001010", ...

Apart from the first four terms seems to be identical with A117248.

Examples

			The Lyndon factorization of the Fibonacci strings of length n = 0..9.
[0] ["1"]
[1] ["0"]
[2] ["01"]
[3] ["01", "0"]
[4] ["01", "001"]
[5] ["01", "00101", "0"]
[6] ["01", "00101", "001", "001"]
[7] ["01", "00101", "0010010100101", "0"]
[8] ["01", "00101", "0010010100101", "00100101", "001", "001"]
[9] ["01", "00101", "0010010100101", "0010010100100101001010010010100101", "0"]
		

Links

• Guy Melançon, Lyndon factorization of infinite words, STACS 96 (Grenoble, 1996), 147-154, Lecture Notes in Comput. Sci., 1046, Springer, Berlin, 1996.
• Wikipedia, Lyndon word

Crossrefs

Cf. A000045, A014707, A074650, A117248, A211100, A352746, A352744.

Programs

Maple

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