login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A320434 Number of length-n quasiperiodic binary strings. 2
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 (list; graph; refs; listen; history; text; internal format)
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..35.

A. Apostolico, M. Farach, and C. S. Iliopoulos, Optimal superprimitivity testing for strings, Info. Proc. Letters 39 (1991), 17-20.

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.

CROSSREFS

Cf. A216215.

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 25 12:01 EST 2020. Contains 332233 sequences. (Running on oeis4.)