cp's OEIS Frontend

A329313 Length of the Lyndon factorization of the reversed binary expansion of n.

%I A329313 #11 Nov 15 2019 09:34:55
%S A329313 0,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,
%T A329313 2,3,2,3,2,4,1,2,3,4,1,3,2,5,1,2,2,3,1,2,2,4,1,2,1,3,1,2,1,6,1,2,2,3,
%U A329313 2,3,2,4,1,3,3,4,2,3,2,5,1,2,2,3,1,4,3
%N A329313 Length of the Lyndon factorization of the reversed binary expansion of n.
%C A329313 We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).
%e A329313 The sequence of reversed binary expansions of the nonnegative integers together with their Lyndon factorizations begins:
%e A329313    0:      () = ()
%e A329313    1:     (1) = (1)
%e A329313    2:    (01) = (01)
%e A329313    3:    (11) = (1)(1)
%e A329313    4:   (001) = (001)
%e A329313    5:   (101) = (1)(01)
%e A329313    6:   (011) = (011)
%e A329313    7:   (111) = (1)(1)(1)
%e A329313    8:  (0001) = (0001)
%e A329313    9:  (1001) = (1)(001)
%e A329313   10:  (0101) = (01)(01)
%e A329313   11:  (1101) = (1)(1)(01)
%e A329313   12:  (0011) = (0011)
%e A329313   13:  (1011) = (1)(011)
%e A329313   14:  (0111) = (0111)
%e A329313   15:  (1111) = (1)(1)(1)(1)
%e A329313   16: (00001) = (00001)
%e A329313   17: (10001) = (1)(0001)
%e A329313   18: (01001) = (01)(001)
%e A329313   19: (11001) = (1)(1)(001)
%e A329313   20: (00101) = (00101)
%t A329313 lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t A329313 lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#1]]&]]]];
%t A329313 Table[If[n==0,0,Length[lynfac[Reverse[IntegerDigits[n,2]]]]],{n,0,30}]
%Y A329313 The non-reversed version is A211100.
%Y A329313 Positions of 1's are A328596.
%Y A329313 The "co" version is A329326.
%Y A329313 Binary Lyndon words are counted by A001037 and ranked by A102659.
%Y A329313 Numbers whose reversed binary expansion is a necklace are A328595.
%Y A329313 Numbers whose reversed binary expansion is a aperiodic are A328594.
%Y A329313 Length of the co-Lyndon factorization of the binary expansion is A329312.
%Y A329313 Cf. A000031, A027375, A059966, A060223, A121016, A211097, A275692, A329131, A329314,  A329317, A329325.
%K A329313 nonn
%O A329313 0,4
%A A329313 _Gus Wiseman_, Nov 11 2019