

A211100


Number of factors in Lyndon factorization of binary expansion of n.


6



1, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 4, 3, 4, 4, 5, 2, 3, 2, 4, 3, 3, 2, 5, 3, 4, 3, 5, 4, 5, 5, 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, 4, 6, 5, 6, 6, 7, 2, 3, 2, 4, 2, 3, 2, 5, 3, 3, 2, 4, 2, 3, 2, 6, 3, 4, 3, 5, 4, 3, 2, 5, 3, 4, 3, 4, 3, 3, 2, 7, 3, 4, 3, 5, 3, 4, 3, 6, 4, 5, 3, 5, 4, 4, 3, 7, 4, 5, 4, 6, 5, 5, 4, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). a(n) = number of factors in Lyndon factorization of binary expansion of n.
It appears that a(n) = k for the first time when n = 2^(k1)+1.


REFERENCES

M. Lothaire, Combinatorics on Words, AddisonWesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
G. Melancon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 3442


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Maple programs for A211100 etc.


EXAMPLE

n=25 has binary expansion 11001, which has Lyndon factorization (1)(1)(001) with three factors, so a(25) = 3.
Here are the Lyndon factorizations for small values of n:
.0.
.1.
.1.0.
.1.1.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.1.0.0.0.
.1.001.
.1.01.0.
.1.011.
.1.1.0.0.
...


CROSSREFS

Cf. A001037 (number of Lyndon words of length m); A102659 (list thereof).
A211095 and A211096 give information about the smallest (or rightmost) factor. Cf. A211097, A211098, A211099.
Sequence in context: A217865 A185166 A276555 * A105264 A063787 A182745
Adjacent sequences: A211097 A211098 A211099 * A211101 A211102 A211103


KEYWORD

nonn


AUTHOR

N. J. A. Sloane, Mar 31 2012


STATUS

approved



