A356959 - OEIS

%I #16 Sep 08 2022 07:53:25

%S 2,4,6,10,14,18,22,26,32,36,40,44,48,52,58,64,72,76,80,84,88,92,98,

%T 102,106,110,114,120,128,134,142,150,160,164,168,172,176,180,186,190,

%U 194,198,202,208,216,220,228,232,236,240,244,248,252,258,266,274,284

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

%C 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.

%H Y. Kobayashi, <a href="https://doi.org/10.1016/0166-218X(88)90078-9">Enumeration of irreducible binary words</a>, Discrete Applied Mathematics 20 (1988), 221-232.

%H L. Schaeffer and J. Shallit, <a href="https://arxiv.org/abs/2209.03266">The first-order theory of binary overlap-free words is decidable</a>, arXiv:2209.03266 [cs.FL], 2022.

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

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

%Y Cf. A007777.

%K nonn

%O 1,1

%A _Jeffrey Shallit_, Sep 06 2022