cp's OEIS Frontend

A329312 Length of the co-Lyndon factorization of the binary expansion of n.

%I A329312 #13 Nov 15 2019 09:34:37
%S A329312 1,1,2,1,2,1,3,1,2,2,3,1,2,1,4,1,2,2,3,1,3,2,4,1,2,1,3,1,2,1,5,1,2,2,
%T A329312 3,2,3,2,4,1,2,3,4,2,3,2,5,1,2,1,3,1,2,2,4,1,2,1,3,1,2,1,6,1,2,2,3,2,
%U A329312 3,2,4,1,3,3,4,2,3,2,5,1,2,2,3,1,4,3
%N A329312 Length of the co-Lyndon factorization of the binary expansion of n.
%C A329312 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).
%C A329312 Also the length of the Lyndon factorization of the inverted binary expansion of n, where the inverted digits are 1 minus the binary digits.
%e A329312 The binary indices of 1..20 together with their co-Lyndon factorizations are:
%e A329312    1:     (1) = (1)
%e A329312    2:    (10) = (10)
%e A329312    3:    (11) = (1)(1)
%e A329312    4:   (100) = (100)
%e A329312    5:   (101) = (10)(1)
%e A329312    6:   (110) = (110)
%e A329312    7:   (111) = (1)(1)(1)
%e A329312    8:  (1000) = (1000)
%e A329312    9:  (1001) = (100)(1)
%e A329312   10:  (1010) = (10)(10)
%e A329312   11:  (1011) = (10)(1)(1)
%e A329312   12:  (1100) = (1100)
%e A329312   13:  (1101) = (110)(1)
%e A329312   14:  (1110) = (1110)
%e A329312   15:  (1111) = (1)(1)(1)(1)
%e A329312   16: (10000) = (10000)
%e A329312   17: (10001) = (1000)(1)
%e A329312   18: (10010) = (100)(10)
%e A329312   19: (10011) = (100)(1)(1)
%e A329312   20: (10100) = (10100)
%t A329312 colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
%t A329312 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 A329312 Table[Length[colynfac[IntegerDigits[n,2]]],{n,100}]
%Y A329312 The non-"co" version is A211100.
%Y A329312 Positions of 1's are A275692.
%Y A329312 The reversed version is A329326.
%Y A329312 Cf. A000031, A001037, A059966, A060223, A211097, A296372, A296658, A329131, A329314, A329318, A329324, A329325.
%K A329312 nonn
%O A329312 1,3
%A A329312 _Gus Wiseman_, Nov 10 2019