A320434 Number of length-n quasiperiodic binary strings.

0, 2, 2, 4, 4, 10, 10, 26, 22, 56, 68, 118, 126, 284, 274, 542, 604, 1144, 1196, 2284, 2340, 4600, 4876, 9010, 9280, 18286, 18476, 35546, 36886, 70320, 72092, 140578, 141736, 276812, 282694, 548164, 555346, 1094778, 1101258, 2165770, 2194012, 4310062, 4345026

Offset: 1

Author

Jeffrey Shallit, Jan 08 2019

Keywords

• nonn

Comments

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.

Examples

			For n = 5 the quasiperiodic strings are 00000, 01010, and their complements.
		

Links

• A. Apostolico, M. Farach, and C. S. Iliopoulos, Optimal superprimitivity testing for strings, Info. Proc. Letters 39 (1991), 17-20.
• Michael S. Branicky, Python program
• Rémy Sigrist, C program for A320434

Crossrefs

Cf. A216215, A320441.

Programs

C

// See Links section.

Python

# see links for faster, bit-based version
from itertools import product
def qp(w):
    for i in range(1, len(w)):
        prefix, covered = w[:i], set()
        for j in range(len(w)-i+1):
            if w[j:j+i] == prefix:
                covered |= set(range(j, j+i))
        if covered == set(range(len(w))):
            return True
    return False
def a(n):
    return 2*sum(1 for w in product("01", repeat=n-1) if qp("0"+"".join(w)))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Mar 20 2022

Formula

a(n) = 2^n - A216215(n). - Rémy Sigrist, Jan 08 2019

Extensions

a(18)-a(30) from Rémy Sigrist, Jan 08 2019

a(31)-a(35) from Rémy Sigrist, Jan 09 2019

a(36) from Michael S. Branicky, Mar 24 2022

a(37)-a(43) from Jinyuan Wang, Jul 11 2025