cp's OEIS Frontend

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

%I A296658 #14 Jan 22 2020 08:08:31
%S A296658 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,
%T A296658 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,
%U A296658 5,6,7,6,7,5,5,6,5,6,7,6,5,6,5,5,6,7,6
%N A296658 Length of the standard Lyndon word factorization of the first n terms of A000002.
%H A296658 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 A296658 The standard Lyndon word factorization of (12211212212211211) is (122)(112122122)(112)(1)(1), so a(17) = 5.
%e A296658 The standard factorizations of initial terms of A000002:
%e A296658 1
%e A296658 12
%e A296658 122
%e A296658 122,1
%e A296658 122,1,1
%e A296658 122,112
%e A296658 122,112,1
%e A296658 122,11212
%e A296658 122,112122
%e A296658 122,112122,1
%e A296658 122,11212212
%e A296658 122,112122122
%e A296658 122,112122122,1
%e A296658 122,112122122,1,1
%e A296658 122,112122122,112
%e A296658 122,112122122,112,1
%e A296658 122,112122122,112,1,1
%e A296658 122,112122122,112,112
%e A296658 122,112122122,1121122
%e A296658 122,112122122,1121122,1
%t A296658 LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
%t A296658 qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],LyndonQ[Take[q,#]]&]];
%t A296658 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 A296658 Table[Length[qit[Nest[kolagrow,1,n]]],{n,150}]
%Y A296658 Row lengths of A329315.
%Y A296658 The "co-" version is A329362.
%Y A296658 Cf. A000002, A001037, A027375, A060223, A088568, A102659, A211100, A281013, A288605, A296372, A296657, A296659, A328596, A329312, A329316, A329317.
%K A296658 nonn
%O A296658 1,4
%A A296658 _Gus Wiseman_, Dec 18 2017