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

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.

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.

Example

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

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 *)

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.

Sequence in context: A106140 A355300 A371452 * A354907 A086342 A274036

Adjacent sequences: A211094 A211095 A211096 * A211098 A211099 A211100

Keyword

nonn

Author

N. J. A. Sloane, Apr 01 2012

Status

approved