cp's OEIS Frontend

A320434 Number of length-n quasiperiodic binary strings.

%I A320434 #37 Jul 12 2025 10:30:34
%S A320434 0,2,2,4,4,10,10,26,22,56,68,118,126,284,274,542,604,1144,1196,2284,
%T A320434 2340,4600,4876,9010,9280,18286,18476,35546,36886,70320,72092,140578,
%U A320434 141736,276812,282694,548164,555346,1094778,1101258,2165770,2194012,4310062,4345026
%N A320434 Number of length-n quasiperiodic binary strings.
%C A320434 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 A320434 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 A320434 Michael S. Branicky, <a href="/A320434/a320434.py.txt">Python program</a>
%H A320434 Rémy Sigrist, <a href="/A320434/a320434.txt">C program for A320434</a>
%F A320434 a(n) = 2^n - A216215(n). - _Rémy Sigrist_, Jan 08 2019
%e A320434 For n = 5 the quasiperiodic strings are 00000, 01010, and their complements.
%o A320434 (C) // See Links section.
%o A320434 (Python) # see links for faster, bit-based version
%o A320434 from itertools import product
%o A320434 def qp(w):
%o A320434     for i in range(1, len(w)):
%o A320434         prefix, covered = w[:i], set()
%o A320434         for j in range(len(w)-i+1):
%o A320434             if w[j:j+i] == prefix:
%o A320434                 covered |= set(range(j, j+i))
%o A320434         if covered == set(range(len(w))):
%o A320434             return True
%o A320434     return False
%o A320434 def a(n):
%o A320434     return 2*sum(1 for w in product("01", repeat=n-1) if qp("0"+"".join(w)))
%o A320434 print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Mar 20 2022
%Y A320434 Cf. A216215, A320441.
%K A320434 nonn
%O A320434 1,2
%A A320434 _Jeffrey Shallit_, Jan 08 2019
%E A320434 a(18)-a(30) from _Rémy Sigrist_, Jan 08 2019
%E A320434 a(31)-a(35) from _Rémy Sigrist_, Jan 09 2019
%E A320434 a(36) from _Michael S. Branicky_, Mar 24 2022
%E A320434 a(37)-a(43) from _Jinyuan Wang_, Jul 11 2025