cp's OEIS Frontend

A329317 Length of the Lyndon factorization of the reversed first n terms of A000002.

%I A329317 #6 Nov 11 2019 21:38:04
%S A329317 1,2,3,2,2,3,3,4,5,4,5,6,5,3,4,4,2,3,4,3,4,3,3,4,4,5,6,5,4,5,5,2,3,3,
%T A329317 4,5,4,5,6,5,3,4,4,5,6,5,6,5,3,4,4,2,3,4,3,4,5,4,3,4,4,5,6,5,6,7,6,4,
%U A329317 5,5,3,4,4,5,6,5,6,5,4,5,6,5,6,7,6,5,6
%N A329317 Length of the Lyndon factorization of the reversed first n terms of A000002.
%C A329317 We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).
%e A329317 The sequence of Lyndon factorizations of the reversed initial terms of A000002 begins:
%e A329317    1: (1)
%e A329317    2: (2)(1)
%e A329317    3: (2)(2)(1)
%e A329317    4: (122)(1)
%e A329317    5: (1122)(1)
%e A329317    6: (2)(1122)(1)
%e A329317    7: (12)(1122)(1)
%e A329317    8: (2)(12)(1122)(1)
%e A329317    9: (2)(2)(12)(1122)(1)
%e A329317   10: (122)(12)(1122)(1)
%e A329317   11: (2)(122)(12)(1122)(1)
%e A329317   12: (2)(2)(122)(12)(1122)(1)
%e A329317   13: (122)(122)(12)(1122)(1)
%e A329317   14: (112212212)(1122)(1)
%e A329317   15: (2)(112212212)(1122)(1)
%e A329317   16: (12)(112212212)(1122)(1)
%e A329317   17: (1121122122121122)(1)
%e A329317   18: (2)(1121122122121122)(1)
%e A329317   19: (2)(2)(1121122122121122)(1)
%e A329317   20: (122)(1121122122121122)(1)
%e A329317 For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so a(13) = 5.
%t A329317 lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t A329317 lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];
%t A329317 kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],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 A329317 kol[n_Integer]:=Nest[kolagrow,{1},n-1];
%t A329317 Table[Length[lynfac[Reverse[kol[n]]]],{n,100}]
%Y A329317 Row-lengths of A329316.
%Y A329317 The non-reversed version is A329315.
%Y A329317 Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.
%K A329317 nonn
%O A329317 1,2
%A A329317 _Gus Wiseman_, Nov 11 2019