login
Number of length-n quasiperiodic binary strings.
3

%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