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

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, 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, 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

Offset: 1

Author

N. J. A. Sloane, Apr 01 2012

Keywords

• nonn

Comments

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,...

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

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

Examples

			Here are the Lyndon factorizations of the first few binary vectors:
.0.
.1.
.0.0.
.01.
.1.0.
.1.1.
.0.0.0.
.001.
.01.0. <- this means that the factorization is (01)(0), for example
.011.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.0.0.0.0.
...
		

References

• M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
• G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..10000
• N. J. A. Sloane, Maple programs for A211097 etc.

Crossrefs

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

Cf. A211095, A211096.

Row-lengths of A329325.

The "co" version is A329400.

Retaining the first digit gives A211100.

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

Numbers whose reversed binary expansion is Lyndon are A328596.

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

Programs

Mathematica

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];
Table[Length[lynfac[Rest[IntegerDigits[n,2]]]],{n,2,50}] (* Gus Wiseman, Nov 14 2019 *)