OFFSET
1,1
COMMENTS
A binary string is overlap-free if it contains no block of the form axaxa, where a in {0,1} and x a possibly empty string.
LINKS
Y. Kobayashi, Enumeration of irreducible binary words, Discrete Applied Mathematics 20 (1988), 221-232.
L. Schaeffer and J. Shallit, The first-order theory of binary overlap-free words is decidable, arXiv:2209.03266 [cs.FL], 2022.
FORMULA
a(n) = Theta(n^c), where c = 1.15501186367066470321... .
EXAMPLE
For example, 010011001011010010 is infinitely extendable to the right, but 010011001011010011 is not (every extension by a word of length 7 gives an overlap).
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Sep 06 2022
STATUS
approved