%I #29 Mar 24 2022 14:51:05
%S 0,2,2,4,4,10,10,26,22,56,68,118,126,284,274,542,604,1144,1196,2284,
%T 2340,4600,4876,9010,9280,18286,18476,35546,36886,70320,72092,140578,
%U 141736,276812,282694,548164
%N Number of length-n quasiperiodic binary strings.
%C A length-n string x is quasiperiodic if some proper prefix t of x can completely cover x by shifting, allowing overlaps. For example, 01010010 is quasiperiodic because it can be covered by shifted occurrences of 010.
%H A. Apostolico, M. Farach, and C. S. Iliopoulos, <a href="https://doi.org/10.1016/0020-0190(91)90056-N">Optimal superprimitivity testing for strings</a>, Info. Proc. Letters 39 (1991), 17-20.
%H Michael S. Branicky, <a href="/A320434/a320434.py.txt">Python program</a>
%H Rémy Sigrist, <a href="/A320434/a320434.txt">C program for A320434</a>
%F a(n) = 2^n - A216215(n). - _Rémy Sigrist_, Jan 08 2019
%e For n = 5 the quasiperiodic strings are 00000, 01010, and their complements.
%o (C) See Links section.
%o (Python) # see links for faster, bit-based version
%o from itertools import product
%o def qp(w):
%o for i in range(1, len(w)):
%o prefix, covered = w[:i], set()
%o for j in range(len(w)-i+1):
%o if w[j:j+i] == prefix:
%o covered |= set(range(j, j+i))
%o if covered == set(range(len(w))):
%o return True
%o return False
%o def a(n):
%o return 2*sum(1 for w in product("01", repeat=n-1) if qp("0"+"".join(w)))
%o print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Mar 20 2022
%Y Cf. A216215, A320441.
%K nonn,more
%O 1,2
%A _Jeffrey Shallit_, Jan 08 2019
%E a(18)-a(30) from _Rémy Sigrist_, Jan 08 2019
%E a(31)-a(35) from _Rémy Sigrist_, Jan 09 2019
%E a(36) from _Michael S. Branicky_, Mar 24 2022