login
A356959
Number of length-n binary strings that can be infinitely extended to the right to form an overlap-free string.
0
2, 4, 6, 10, 14, 18, 22, 26, 32, 36, 40, 44, 48, 52, 58, 64, 72, 76, 80, 84, 88, 92, 98, 102, 106, 110, 114, 120, 128, 134, 142, 150, 160, 164, 168, 172, 176, 180, 186, 190, 194, 198, 202, 208, 216, 220, 228, 232, 236, 240, 244, 248, 252, 258, 266, 274, 284
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
Cf. A007777.
Sequence in context: A125964 A288526 A139544 * A062091 A100143 A234941
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Sep 06 2022
STATUS
approved