A352745 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

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.

LINKS

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

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

EXAMPLE

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