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

Table of n, a(n) for n=1..57.

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

Adjacent sequences: A356956 A356957 A356958 * A356960 A356961 A356962

Keyword

nonn

Author

Jeffrey Shallit, Sep 06 2022

Status

approved