A296658 Length of the standard Lyndon word factorization of the first n terms of A000002.

1, 1, 1, 2, 3, 2, 3, 2, 2, 3, 2, 2, 3, 4, 3, 4, 5, 4, 3, 4, 3, 4, 5, 4, 5, 3, 3, 4, 5, 4, 5, 6, 5, 6, 4, 4, 5, 4, 4, 5, 6, 5, 6, 4, 4, 5, 4, 5, 6, 5, 6, 7, 6, 4, 5, 4, 4, 5, 6, 5, 6, 4, 4, 5, 4, 4, 5, 6, 5, 6, 7, 6, 7, 5, 5, 6, 5, 6, 7, 6, 5, 6, 5, 5, 6, 7, 6

Offset

1,4

Links

Table of n, a(n) for n=1..87.

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

Row lengths of A329315.

The "co-" version is A329362.

Cf. A000002, A001037, A027375, A060223, A088568, A102659, A211100, A281013, A288605, A296372, A296657, A296659, A328596, A329312, A329316, A329317.

Sequence in context: A244228 A023397 A258115 * A276862 A371442 A175066

Adjacent sequences: A296655 A296656 A296657 * A296659 A296660 A296661

Keyword

nonn

Author

Gus Wiseman, Dec 18 2017

Status

approved