OFFSET
1,4
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 standard Lyndon word factorization of (12211212212211211) is (122)(112122122)(112)(1)(1), so a(17) = 5.
The standard factorizations of initial terms of A000002:
1
12
122
122,1
122,1,1
122,112
122,112,1
122,11212
122,112122
122,112122,1
122,11212212
122,112122122
122,112122122,1
122,112122122,1,1
122,112122122,112
122,112122122,112,1
122,112122122,112,1,1
122,112122122,112,112
122,112122122,1121122
122,112122122,1121122,1
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[qit[Nest[kolagrow, 1, n]]], {n, 150}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 18 2017
STATUS
approved