proposed

approved

editing

proposed

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

The reverse reversed version is A329316.

All rows belong to A329314co.

Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A329314, A329317, A329325.

nonn,changed,tabf

Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A329317, A329325.

allocated for Gus WisemanIrregular triangle read by rows where row n gives the sequence of lengths of components of the unsorted Lyndon factorization of the first n terms of A000002.

1, 2, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 3, 5, 3, 6, 3, 6, 1, 3, 8, 3, 9, 3, 9, 1, 3, 9, 1, 1, 3, 9, 3, 3, 9, 3, 1, 3, 9, 3, 1, 1, 3, 9, 3, 3, 3, 9, 7, 3, 9, 7, 1, 3, 9, 9, 3, 9, 9, 1, 3, 9, 9, 1, 1, 3, 9, 9, 3, 3, 9, 9, 3, 1, 3, 9, 14, 3, 9, 15, 3, 9, 15, 1, 3

1,2

There are no repeated rows, as row n has sum n.

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).

It appears that some numbers (such as 4) never appear in the sequence.

Triangle begins:

1: (1)

2: (2)

3: (3)

4: (3,1)

5: (3,1,1)

6: (3,3)

7: (3,3,1)

8: (3,5)

9: (3,6)

10: (3,6,1)

11: (3,8)

12: (3,9)

13: (3,9,1)

14: (3,9,1,1)

15: (3,9,3)

16: (3,9,3,1)

17: (3,9,3,1,1)

18: (3,9,3,3)

19: (3,9,7)

20: (3,9,7,1)

For example, the first 10 terms of A000002 are (1221121221), with Lyndon factorization (122)(112122)(1), so row 10 is (3,6,1).

lynQ[q_]:=Array[Union[{q, RotateRight[q, #1]}]=={q, RotateRight[q, #1]}&, Length[q]-1, 1, And];

lynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[lynfac[Drop[q, i]], Take[q, i]]][Last[Select[Range[Length[q]], lynQ[Take[q, #1]]&]]]];

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]]];

kol[n_Integer]:=Nest[kolagrow, {1}, n-1];

Table[Length/@lynfac[kol[n]], {n, 100}]

Row lengths are A296658.

All rows belong to A329314co.

The reverse version is A329316.

Cf. A000002, A000031, A001037, A027375, A059966, A060223, A102659, A211100, A296372, A329317, A329325.

allocated

nonn

Gus Wiseman, Nov 11 2019

approved

editing

allocated for Gus Wiseman

allocated

approved