A329362 Length of the co-Lyndon factorization of the first n terms of A000002.

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

Offset: 0

Author

Gus Wiseman, Nov 12 2019

Keywords

• nonn

Comments

The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). 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, (1001) has sorted co-Lyndon factorization (1)(100).

Examples

			The co-Lyndon factorizations of the initial terms of A000002:
                      () = 0
                     (1) = (1)
                    (12) = (1)(2)
                   (122) = (1)(2)(2)
                  (1221) = (1)(221)
                 (12211) = (1)(2211)
                (122112) = (1)(2211)(2)
               (1221121) = (1)(221121)
              (12211212) = (1)(221121)(2)
             (122112122) = (1)(221121)(2)(2)
            (1221121221) = (1)(221121)(221)
           (12211212212) = (1)(221121)(221)(2)
          (122112122122) = (1)(221121)(221)(2)(2)
         (1221121221221) = (1)(221121)(221)(221)
        (12211212212211) = (1)(221121)(2212211)
       (122112122122112) = (1)(221121)(2212211)(2)
      (1221121221221121) = (1)(221121)(221221121)
     (12211212212211211) = (1)(221121)(2212211211)
    (122112122122112112) = (1)(221121)(2212211211)(2)
   (1221121221221121122) = (1)(221121)(2212211211)(2)(2)
  (12211212212211211221) = (1)(221121)(2212211211)(221)
		

Crossrefs

The non-"co" version is A296658.

Cf. A000002, A001037, A060223, A088568, A102659, A275692, A329312, A329315, A329317, A329318.

Programs

Mathematica

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]:=If[n==0,{},Nest[kolagrow,{1},n-1]];
colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]]@Last[Select[Range[Length[q]],colynQ[Take[q,#]]&]]];
Table[Length[colynfac[kol[n]]],{n,0,100}]