cp's OEIS Frontend

A329316 Irregular triangle read by rows where row n gives the sequence of lengths of components of the Lyndon factorization of the reversed first n terms of A000002.

%I A329316 #5 Nov 11 2019 21:37:55
%S A329316 1,1,1,1,1,1,3,1,4,1,1,4,1,2,4,1,1,2,4,1,1,1,2,4,1,3,2,4,1,1,3,2,4,1,
%T A329316 1,1,3,2,4,1,3,3,2,4,1,9,4,1,1,9,4,1,2,9,4,1,16,1,1,16,1,1,1,16,1,3,
%U A329316 16,1,1,3,16,1,5,16,1,6,16,1,1,6,16,1,2,6
%N A329316 Irregular triangle read by rows where row n gives the sequence of lengths of components of the Lyndon factorization of the reversed first n terms of A000002.
%C A329316 There are no repeated rows, as row n has sum n.
%C A329316 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).
%C A329316 It appears that some numbers (such as 10) never appear in the sequence.
%e A329316 Triangle begins:
%e A329316    1: (1)
%e A329316    2: (1,1)
%e A329316    3: (1,1,1)
%e A329316    4: (3,1)
%e A329316    5: (4,1)
%e A329316    6: (1,4,1)
%e A329316    7: (2,4,1)
%e A329316    8: (1,2,4,1)
%e A329316    9: (1,1,2,4,1)
%e A329316   10: (3,2,4,1)
%e A329316   11: (1,3,2,4,1)
%e A329316   12: (1,1,3,2,4,1)
%e A329316   13: (3,3,2,4,1)
%e A329316   14: (9,4,1)
%e A329316   15: (1,9,4,1)
%e A329316   16: (2,9,4,1)
%e A329316   17: (16,1)
%e A329316   18: (1,16,1)
%e A329316   19: (1,1,16,1)
%e A329316   20: (3,16,1)
%e A329316 For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so row 13 is (3,3,2,4,1).
%t A329316 lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t A329316 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 A329316 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 A329316 kol[n_Integer]:=Nest[kolagrow,{1},n-1];
%t A329316 Table[Length/@lynfac[Reverse[kol[n]]],{n,100}]
%Y A329316 Row lengths are A329317.
%Y A329316 The non-reversed version is A329315.
%Y A329316 Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.
%K A329316 nonn,tabf
%O A329316 0,7
%A A329316 _Gus Wiseman_, Nov 11 2019