A356959 Number of length-n binary strings that can be infinitely extended to the right to form an overlap-free string.

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

Author

Jeffrey Shallit, Sep 06 2022

Keywords

• nonn

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.

Examples

			For example, 010011001011010010 is infinitely extendable to the right, but 010011001011010011 is not (every extension by a word of length 7 gives an overlap).
		

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.

Crossrefs

Cf. A007777.

Formula

a(n) = Theta(n^c), where c = 1.15501186367066470321... .