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.

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, 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, 16, 1, 1, 3, 16, 1, 5, 16, 1, 6, 16, 1, 1, 6, 16, 1, 2, 6

Offset

0,7

Comments

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 10) never appear in the sequence.

Links

Table of n, a(n) for n=0..83.

Example

Triangle begins:
   1: (1)
   2: (1,1)
   3: (1,1,1)
   4: (3,1)
   5: (4,1)
   6: (1,4,1)
   7: (2,4,1)
   8: (1,2,4,1)
   9: (1,1,2,4,1)
  10: (3,2,4,1)
  11: (1,3,2,4,1)
  12: (1,1,3,2,4,1)
  13: (3,3,2,4,1)
  14: (9,4,1)
  15: (1,9,4,1)
  16: (2,9,4,1)
  17: (16,1)
  18: (1,16,1)
  19: (1,1,16,1)
  20: (3,16,1)
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).

Mathematica

lynQ[q_]:=Array[Union[{q, RotateRight[q, #]}]=={q, RotateRight[q, #]}&, 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, #]]&]]]];
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[Reverse[kol[n]]], {n, 100}]

Crossrefs

Row lengths are A329317.

The non-reversed version is A329315.

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

Sequence in context: A320640 A055187 A217780 * A109411 A302240 A130307

Adjacent sequences: A329313 A329314 A329315 * A329317 A329318 A329319

Keyword

nonn,tabf

Author

Gus Wiseman, Nov 11 2019

Status

approved