A211097 - OEIS

%I #29 Mar 30 2023 09:16:19

%S 1,1,2,1,2,2,3,1,2,1,3,2,3,3,4,1,2,1,3,2,2,1,4,2,3,2,4,3,4,4,5,1,2,1,

%T 3,1,2,1,4,2,3,1,3,2,2,1,5,2,3,2,4,3,3,2,5,3,4,3,5,4,5,5,6,1,2,1,3,1,

%U 2,1,4,2,2,1,3,1,2,1,5,2,3,2,4,3,2,1,4,2,3,2,3,2,2,1,6,2,3,2,4,2,3,2,5,3,4,2,4,3,3,2,6,3,4,3,5,4,4,3,6,4,5

%N Number of factors in Lyndon factorization of binary vectors of lengths 1, 2, 3, ...

%C Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). Here we look at the Lyndon factorizations of the binary vectors 0,1, 00,01,10,11, 000,001,010,011,100,101,110,111, 0000,...

%C For the largest (or leftmost) factor see A211098, A211099.

%C The smallest (or rightmost) factors are given by A211095 and A211096, offset by 2.

%D M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.

%D G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42

%H N. J. A. Sloane, <a href="/A211097/b211097.txt">Table of n, a(n) for n = 1..10000</a>

%H N. J. A. Sloane, <a href="/A211097/a211097.txt">Maple programs for A211097 etc.</a>

%e Here are the Lyndon factorizations of the first few binary vectors:

%e .0.

%e .1.

%e .0.0.

%e .01.

%e .1.0.

%e .1.1.

%e .0.0.0.

%e .001.

%e .01.0. <- this means that the factorization is (01)(0), for example

%e .011.

%e .1.0.0.

%e .1.01.

%e .1.1.0.

%e .1.1.1.

%e .0.0.0.0.

%e ...

%t lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];

%t lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];

%t Table[Length[lynfac[Rest[IntegerDigits[n,2]]]],{n,2,50}] (* _Gus Wiseman_, Nov 14 2019 *)

%Y A211098 and A211099 give information about the largest (or leftmost) factor.

%Y Cf. A211095, A211096.

%Y Row-lengths of A329325.

%Y The "co" version is A329400.

%Y Retaining the first digit gives A211100.

%Y Binary Lyndon words are counted by A001037 and constructed by A102659.

%Y Numbers whose reversed binary expansion is Lyndon are A328596.

%Y Cf. A059966, A060223, A275692, A329312, A329313, A329314, A329326.

%K nonn

%O 1,3

%A _N. J. A. Sloane_, Apr 01 2012