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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 18 2017
STATUS
approved