cp's OEIS Frontend

A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.

%I A334029 #6 Apr 15 2020 09:53:07
%S A334029 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 A334029 1,1,2,1,1,1,2,2,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 A334029 1,1,1,1,2,1,1,1,2,1,1,1,2,2,2,2,3,1,2
%N A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.
%C A334029 We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1,0,0,1) has co-Lyndon factorization {(1),(1,0,0)}.
%C A334029 A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of 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 A334029 The 441st composition in standard order is (1,2,1,1,3,1), with co-Lyndon factorization {(1),(3,1),(2,1,1)}, so a(441) = 3.
%t A334029 stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A334029 colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#1],q}]=={RotateRight[q,#1],q}&,Length[q]-1,1,And];
%t A334029 colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],colynQ[Take[q,#1]]&]]]]
%t A334029 Table[Length[colynfac[stc[n]]],{n,0,100}]
%Y A334029 The dual version is A329312.
%Y A334029 The version for binary expansion is (also) A329312.
%Y A334029 The version for reversed binary expansion is A329326.
%Y A334029 Binary Lyndon/co-Lyndon words are counted by A001037.
%Y A334029 Necklaces covering an initial interval are A019536.
%Y A334029 Lyndon/co-Lyndon compositions are counted by A059966
%Y A334029 Length of Lyndon factorization of binomial expansion is A211100.
%Y A334029 Numbers whose prime signature is a necklace are A329138.
%Y A334029 Length of Lyndon factorization of reversed binary expansion is A329313.
%Y A334029 A list of all binary co-Lyndon words is A329318.
%Y A334029 All of the following pertain to compositions in standard order (A066099):
%Y A334029 - Length is A000120.
%Y A334029 - Necklaces are A065609.
%Y A334029 - Sum is A070939.
%Y A334029 - Runs are counted by A124767.
%Y A334029 - Rotational symmetries are counted by A138904.
%Y A334029 - Strict compositions are A233564.
%Y A334029 - Constant compositions are A272919.
%Y A334029 - Lyndon compositions are A275692.
%Y A334029 - Co-Lyndon compositions are A326774.
%Y A334029 - Aperiodic compositions are A328594.
%Y A334029 - Reversed co-necklaces are A328595.
%Y A334029 - Rotational period is A333632.
%Y A334029 - Co-necklaces are A333764.
%Y A334029 - Co-Lyndon factorizations are counted by A333765.
%Y A334029 - Lyndon factorizations are counted by A333940.
%Y A334029 - Reversed necklaces are A333943.
%Y A334029 - Co-necklaces are A334028.
%Y A334029 Cf. A034691, A060223, A102659, A211097, A292884, A296372, A328596, A329358, A329359, A329362, A329400, A329401, A333939.
%K A334029 nonn
%O A334029 0,4
%A A334029 _Gus Wiseman_, Apr 14 2020