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