A296659 Length of the final word in the standard Lyndon word factorization of the first n terms of A000002.

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

Author

Gus Wiseman, Dec 18 2017

Keywords

• nonn

Examples

			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.
		

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.

Crossrefs

Cf. A000002, A027375, A088568, A102659, A228369, A281013, A288605, A296372, A296657, A296658.

Programs

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