A216214 - OEIS

%I #21 Jan 08 2019 19:11:42

%S 1,2,2,4,6,8,16,24,46,84,160,300,588,1136,2236,4388,8690

%N Number of (strongly) superprimitive binary sequences of length n.

%C 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.

%H A. Apostolico, M. Farach, and C. S. Iliopoulos, <a href="https://doi.org/10.1016/0020-0190(91)90056-N">Optimal superprimitivity testing for strings</a>, Info. Proc. Letters 39 (1991), 17-20.

%e a(6) = 16 because the 8 strings

%e 000001,

%e 000011,

%e 000101,

%e 000111,

%e 001011,

%e 001111,

%e 010111,

%e 011111

%e and their complements are strongly superprimitive.

%K nonn,more

%O 0,2

%A _Jeffrey Shallit_, Mar 13 2013