cp's OEIS Frontend

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

%I A334297 #7 Apr 28 2020 00:14:58
%S A334297 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,
%T A334297 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,
%U A334297 1,1,2,1,2,1,1,1,2,1,2,1,2,1,2,1,3,1,2
%N A334297 Length of the Lyndon factorization of the reversed n-th composition in standard order.
%C A334297 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).
%C A334297 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.
%e A334297 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.
%t A334297 stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A334297 lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t A334297 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 A334297 Table[Length[lynfac[Reverse[stc[n]]]],{n,0,100}]
%Y A334297 The non-reversed version is A329312.
%Y A334297 The version for binary indices is A329313 (also the "co-" version).
%Y A334297 Positions of 1's are A334265 (reversed Lyndon words).
%Y A334297 Binary Lyndon words are counted by A001037 and ranked by A102659.
%Y A334297 Lyndon compositions are counted by A059966 and ranked by A275692.
%Y A334297 Normal Lyndon sequences are counted by A060223 (row sums of A296372).
%Y A334297 All of the following pertain to compositions in standard order (A066099):
%Y A334297 - Length is A000120.
%Y A334297 - Necklaces are A065609.
%Y A334297 - Sum is A070939.
%Y A334297 - Reverse is A228351 (triangle).
%Y A334297 - Strict compositions are A233564.
%Y A334297 - Constant compositions are A272919.
%Y A334297 - Lyndon words are A275692.
%Y A334297 - Co-Lyndon words are A326774.
%Y A334297 - Reversed co-Lyndon words are A328596.
%Y A334297 - Aperiodic compositions are A328594.
%Y A334297 - Distinct rotations are counted by A333632.
%Y A334297 - Lyndon factorizations are counted by A333940.
%Y A334297 - Length of co-Lyndon factorization is A334029.
%Y A334297 Cf. A027375, A211097, A211100, A328595, A329314, A329317.
%K A334297 nonn
%O A334297 0,4
%A A334297 _Gus Wiseman_, Apr 25 2020