login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216214 Number of (strongly) superprimitive binary sequences of length n. 1
1, 2, 2, 4, 6, 8, 16, 24, 46, 84, 160, 300, 588, 1136, 2236, 4388, 8690 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

A string x of length n is (weakly) quasiperiodic if there is a string w of length < n for which copies can be placed (possibly overlapping; possibly hanging off the left and right ends of x) that completely cover x.  For example, x = 001101 is weakly quasiperiodic with quasiperiod w = 0110; three copies of w suffice to cover x.  A string is (strongly) superprimitive if it is not weakly quasiperiodic.

LINKS

Table of n, a(n) for n=0..16.

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

EXAMPLE

a(6) = 16 because the 8 strings

000001,

000011,

000101,

000111,

001011,

001111,

010111,

011111

and their complements are strongly superprimitive.

CROSSREFS

Sequence in context: A255710 A239851 A153958 * A269298 A153964 A001010

Adjacent sequences:  A216211 A216212 A216213 * A216215 A216216 A216217

KEYWORD

nonn,more

AUTHOR

Jeffrey Shallit, Mar 13 2013

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 October 23 09:28 EDT 2019. Contains 328345 sequences. (Running on oeis4.)