A211099 Largest (i.e., leftmost) Lyndon word in Lyndon factorization of binary vectors of lengths 1, 2, 3, ... (written using 1's and 2's rather than 0's and 1's, since numbers > 0 in the OEIS cannot begin with 0).

1, 2, 1, 12, 2, 2, 1, 112, 12, 122, 2, 2, 2, 2, 1, 1112, 112, 1122, 12, 12, 122, 1222, 2, 2, 2, 2, 2, 2, 2, 2, 1, 11112, 1112, 11122, 112, 11212, 1122, 11222, 12, 12, 12, 12122, 122, 122, 1222, 12222, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 111112, 11112, 111122, 1112, 111212, 11122, 111222, 112, 112, 11212, 112122, 1122, 112212, 11222, 112222, 12

Offset

1,2

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

See A211097, A211099, A211100 for further information, including Maple code.

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

Table of n, a(n) for n=1..79.

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.
.011.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.0.0.0.0.
...
The real sequence (written with 0's and 1's rather than 1's and 2's) is:
0, 1, 0, 01, 1, 1, 0, 001, 01, 011, 1, 1, 1, 1, 0, 0001, 001, 0011, 01, 01, 011, 0111, 1, 1, 1, 1, 1, 1, 1, 1, 0, 00001, 0001, 00011, 001, 00101, 0011, 00111, 01, 01, 01, 01011, 011, 011, 0111, 01111, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 000001, 00001, ...

Crossrefs

Cf. A001037 (number of Lyndon words of length m); A102659 (list thereof), A211100.

Cf. A211095-A211099.

Sequence in context: A288594 A285645 A358111 * A058734 A213057 A103187

Adjacent sequences: A211096 A211097 A211098 * A211100 A211101 A211102

Keyword

nonn

Author

N. J. A. Sloane, Apr 01 2012

Status

approved