A334297 Length of the Lyndon factorization of the reversed n-th composition in standard order.

0, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 3, 4, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 3, 2, 3, 3, 4, 5, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 4, 3, 4, 4, 5, 6, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2

Offset: 0

Author

Gus Wiseman, Apr 25 2020

Keywords

• nonn

Comments

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

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

Examples

			The 12345th composition is (1,7,1,1,3,1), with reverse (1,3,1,1,7,1), with Lyndon factorization ((1),(1,3),(1,1,7)), so a(12345) = 3.
		

Crossrefs

The non-reversed version is A329312.

The version for binary indices is A329313 (also the "co-" version).

Positions of 1's are A334265 (reversed Lyndon words).

Binary Lyndon words are counted by A001037 and ranked by A102659.

Lyndon compositions are counted by A059966 and ranked by A275692.

Normal Lyndon sequences are counted by A060223 (row sums of A296372).

All of the following pertain to compositions in standard order (A066099):

- Length is A000120.

- Necklaces are A065609.

- Sum is A070939.

- Reverse is A228351 (triangle).

- Strict compositions are A233564.

- Constant compositions are A272919.

- Lyndon words are A275692.

- Co-Lyndon words are A326774.

- Reversed co-Lyndon words are A328596.

- Aperiodic compositions are A328594.

- Distinct rotations are counted by A333632.

- Lyndon factorizations are counted by A333940.

- Length of co-Lyndon factorization is A334029.

Cf. A027375, A211097, A211100, A328595, A329314, A329317.

Programs

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
lynQ[q_]:=Length[q]==0||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,#]]&]]]];
Table[Length[lynfac[Reverse[stc[n]]]],{n,0,100}]