login
A296659
Length of the final word in the standard Lyndon word factorization of the first n terms of A000002.
1
1, 2, 3, 1, 1, 3, 1, 5, 6, 1, 8, 9, 1, 1, 3, 1, 1, 3, 7, 1, 9, 1, 1, 3, 1, 14, 15, 1, 1, 3, 1, 1, 3, 1, 8, 9, 1, 11, 12, 1, 1, 3, 1, 17, 18, 1, 20, 1, 1, 3, 1, 1, 3, 27, 1, 29, 30, 1, 1, 3, 1, 35, 36, 1, 38, 39, 1, 1, 3, 1, 1, 3, 1, 8, 9, 1, 11, 1, 1, 3, 15, 1
OFFSET
1,2
LINKS
Frédérique Bassino, Julien Clement, and Cyril Nicaud, The standard factorization of Lyndon words: an average point of view, Discrete Mathematics, 290-1, (2005), 1-25.
EXAMPLE
The sequence of final words begins: 1, 12, 122, 1, 1, 112, 1, 11212, 112122, 1, 11212212, 112122122, 1, 1, 112, 1, 1, 112, 1121122, 1, 112112212, 1, 1, 112, 1, 11211221211212, 112112212112122, 1, 1, 112.
MATHEMATICA
LyndonQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And]&&Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
qit[q_]:=If[#===Length[q], {q}, Prepend[qit[Drop[q, #]], Take[q, #]]]&[Max@@Select[Range[Length[q]], LyndonQ[Take[q, #]]&]];
kolagrow[q_]:=If[Length[q]<2, Take[{1, 2}, Length[q]+1], Append[q, Switch[{q[[Length[Split[q]]]], Part[q, -2], Last[q]}, {1, 1, 1}, 0, {1, 1, 2}, 1, {1, 2, 1}, 2, {1, 2, 2}, 0, {2, 1, 1}, 2, {2, 1, 2}, 2, {2, 2, 1}, 1, {2, 2, 2}, 1]]];
Table[Length[Last[qit[Nest[kolagrow, 1, n]]]], {n, 150}]
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 18 2017
STATUS
approved