|
%I #8 Jan 22 2020 07:20:45
%S 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,
%T 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,
%U 36,1,38,39,1,1,3,1,1,3,1,8,9,1,11,1,1,3,15,1
%N Length of the final word in the standard Lyndon word factorization of the first n terms of A000002.
%H Frédérique Bassino, Julien Clement, and Cyril Nicaud, <a href="https://doi.org/10.1016/j.disc.2004.11.002">The standard factorization of Lyndon words: an average point of view</a>, Discrete Mathematics, 290-1, (2005), 1-25.
%e 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.
%t LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
%t qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],LyndonQ[Take[q,#]]&]];
%t 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]]];
%t Table[Length[Last[qit[Nest[kolagrow,1,n]]]],{n,150}]
%Y Cf. A000002, A027375, A088568, A102659, A228369, A281013, A288605, A296372, A296657, A296658.
%K nonn
%O 1,2
%A _Gus Wiseman_, Dec 18 2017
|
