cp's OEIS Frontend

A329400 Length of the co-Lyndon factorization of the binary expansion of n with the most significant (first) digit removed.

%I A329400 #6 Nov 16 2019 13:48:41
%S A329400 0,1,1,2,2,1,2,3,3,2,3,1,2,1,3,4,4,3,4,2,3,2,4,1,2,2,3,1,2,1,4,5,5,4,
%T A329400 5,3,4,3,5,2,3,3,4,2,3,2,5,1,2,2,3,1,3,2,4,1,2,1,3,1,2,1,5,6,6,5,6,4,
%U A329400 5,4,6,3,4,4,5,3,4,3,6,2,3,3,4,2,4,3,5
%N A329400 Length of the co-Lyndon factorization of the binary expansion of n with the most significant (first) digit removed.
%C A329400 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 A329400 Decapitated binary expansions of 1..20 together with their co-Lyndon factorizations:
%e A329400    1:     () =
%e A329400    2:    (0) = (0)
%e A329400    3:    (1) = (1)
%e A329400    4:   (00) = (0)(0)
%e A329400    5:   (01) = (0)(1)
%e A329400    6:   (10) = (10)
%e A329400    7:   (11) = (1)(1)
%e A329400    8:  (000) = (0)(0)(0)
%e A329400    9:  (001) = (0)(0)(1)
%e A329400   10:  (010) = (0)(10)
%e A329400   11:  (011) = (0)(1)(1)
%e A329400   12:  (100) = (100)
%e A329400   13:  (101) = (10)(1)
%e A329400   14:  (110) = (110)
%e A329400   15:  (111) = (1)(1)(1)
%e A329400   16: (0000) = (0)(0)(0)(0)
%e A329400   17: (0001) = (0)(0)(0)(1)
%e A329400   18: (0010) = (0)(0)(10)
%e A329400   19: (0011) = (0)(0)(1)(1)
%e A329400   20: (0100) = (0)(100)
%t A329400 colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
%t A329400 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 A329400 Table[If[n==0,0,Length[colynfac[Rest[IntegerDigits[n,2]]]]],{n,30}]
%Y A329400 The non-"co" version is A211097.
%Y A329400 The version involving all digits is A329312.
%Y A329400 Lyndon and co-Lyndon compositions are (both) counted by A059966.
%Y A329400 Numbers whose reversed binary expansion is Lyndon are A328596.
%Y A329400 Numbers whose binary expansion is co-Lyndon are A275692.
%Y A329400 Numbers whose decapitated binary expansion is co-Lyndon are A329401.
%Y A329400 Cf. A001037, A060223, A102659, A211100, A329313, A329318, A329326, A329395.
%K A329400 nonn
%O A329400 1,4
%A A329400 _Gus Wiseman_, Nov 16 2019