cp's OEIS Frontend

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

%I A329362 #4 Nov 13 2019 08:18:27
%S A329362 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,
%T A329362 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,
%U A329362 6,7,6,5,6,5,6,7,6,7,5,5,6,7,6,7,8,7,6,7
%N A329362 Length of the co-Lyndon factorization of the first n terms of A000002.
%C A329362 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).
%e A329362 The co-Lyndon factorizations of the initial terms of A000002:
%e A329362                       () = 0
%e A329362                      (1) = (1)
%e A329362                     (12) = (1)(2)
%e A329362                    (122) = (1)(2)(2)
%e A329362                   (1221) = (1)(221)
%e A329362                  (12211) = (1)(2211)
%e A329362                 (122112) = (1)(2211)(2)
%e A329362                (1221121) = (1)(221121)
%e A329362               (12211212) = (1)(221121)(2)
%e A329362              (122112122) = (1)(221121)(2)(2)
%e A329362             (1221121221) = (1)(221121)(221)
%e A329362            (12211212212) = (1)(221121)(221)(2)
%e A329362           (122112122122) = (1)(221121)(221)(2)(2)
%e A329362          (1221121221221) = (1)(221121)(221)(221)
%e A329362         (12211212212211) = (1)(221121)(2212211)
%e A329362        (122112122122112) = (1)(221121)(2212211)(2)
%e A329362       (1221121221221121) = (1)(221121)(221221121)
%e A329362      (12211212212211211) = (1)(221121)(2212211211)
%e A329362     (122112122122112112) = (1)(221121)(2212211211)(2)
%e A329362    (1221121221221121122) = (1)(221121)(2212211211)(2)(2)
%e A329362   (12211212212211211221) = (1)(221121)(2212211211)(221)
%t A329362 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]]]
%t A329362 kol[n_Integer]:=If[n==0,{},Nest[kolagrow,{1},n-1]];
%t A329362 colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
%t A329362 colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]]@Last[Select[Range[Length[q]],colynQ[Take[q,#]]&]]];
%t A329362 Table[Length[colynfac[kol[n]]],{n,0,100}]
%Y A329362 The non-"co" version is A296658.
%Y A329362 Cf. A000002, A001037, A060223, A088568, A102659, A275692, A329312, A329315, A329317, A329318.
%K A329362 nonn
%O A329362 0,3
%A A329362 _Gus Wiseman_, Nov 12 2019