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

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

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

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

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, Maple programs for A211097 etc.

Crossrefs

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

Cf. A211095-A211099.