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

Offset

1,2

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.

Links

Table of n, a(n) for n=1..36.

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

Formula

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

Example

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

Prog

(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

Crossrefs

Cf. A216215, A320441.

Sequence in context: A286088 A005293 A287488 * A329394 A057784 A209284

Adjacent sequences: A320431 A320432 A320433 * A320435 A320436 A320437

Keyword

nonn,more

Author

Jeffrey Shallit, 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

Status

approved