A296658 - OEIS

%I #14 Jan 22 2020 08:08:31

%S 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 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 5,6,7,6,7,5,5,6,5,6,7,6,5,6,5,5,6,7,6

%N Length of 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 standard Lyndon word factorization of (12211212212211211) is (122)(112122122)(112)(1)(1), so a(17) = 5.

%e The standard factorizations of initial terms of A000002:

%e 1

%e 12

%e 122

%e 122,1

%e 122,1,1

%e 122,112

%e 122,112,1

%e 122,11212

%e 122,112122

%e 122,112122,1

%e 122,11212212

%e 122,112122122

%e 122,112122122,1

%e 122,112122122,1,1

%e 122,112122122,112

%e 122,112122122,112,1

%e 122,112122122,112,1,1

%e 122,112122122,112,112

%e 122,112122122,1121122

%e 122,112122122,1121122,1

%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[qit[Nest[kolagrow,1,n]]],{n,150}]

%Y Row lengths of A329315.

%Y The "co-" version is A329362.

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

%K nonn

%O 1,4

%A _Gus Wiseman_, Dec 18 2017