A320441 -id:A320441 - cp's OEIS frontend

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

Jeffrey Shallit, Jan 08 2019

nonn

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.

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

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

Cf. A216215, A320441.

C
```
// See Links section.
```

# 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

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

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

A366160 Numbers whose binary expansion is not quasiperiodic.

Original entry on oeis.org

1, 2, 4, 5, 6, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 37, 38, 39, 40, 41, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79

Offset: 1

Darío Clavijo, Oct 02 2023

See A320441 for the definition of quasiperiodic.
All numbers 2^k + 1 >= 5 are terms (A000051).
All powers of 2 are terms (A000079).

Cf. A000051, A000079, A000225, A320441 (complement).

A000225 = lambda n: (1 << n) - 1
def isA320441(k):
  # Code after Michael S. Branicky, Mar 24 2022 in A320434.
  tt, l = 1, k.bit_length()
  for x in range(0, l + 1):
    m = A000225(x)
    t = k & m
    if (t != tt):
      if (t == k): return False
      r = k
      for g in range(0, x):
        r >>= 1
        if (r & m == t) and (r == t): return True
      tt = t
print([n for n in range(1,80) if not isA320441(n)])

A369347 Numbers whose decimal expansion is quasiperiodic.

Original entry on oeis.org

11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333, 444, 555, 666, 777, 888, 999, 1010, 1111, 1212, 1313, 1414, 1515, 1616, 1717, 1818, 1919, 2020, 2121, 2222, 2323, 2424, 2525, 2626, 2727, 2828, 2929, 3030, 3131, 3232, 3333, 3434, 3535, 3636, 3737, 3838, 3939

Offset: 1

Rémy Sigrist, Jan 21 2024

The decimal representation of a term (ignoring leading zeros) can be covered by (possibly overlapping) occurrences of one of its proper prefixes.
This sequence contains, among others, A020338 and A239019.
The first term that does not belong to A239019 is a(109) = 10101.

			The number 10101101 belongs to this sequence as its decimal expansion can be covered by copies of its proper prefix 101:
      101
        101
           101
      ........
      10101101

Index entries for sequences related to decimal expansion of n

Cf. A020338, A239019, A320441 (binary analog).

is(w) = { my (tt=0); for (l=1, oo, my (t=w%(10^l)); if (t!=tt, if (t==w, return (0)); my (r=w, g=l); while (g-->=0 && r>=t, r \= 10; if (r%(10^l)==t, if (r==t, return (1), g=l))); tt = t)) }

cp's OEIS Frontend

A320434 Number of length-n quasiperiodic binary strings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Python

Formula

Extensions

A366160 Numbers whose binary expansion is not quasiperiodic.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

A369347 Numbers whose decimal expansion is quasiperiodic.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI