A216215 - OEIS

A216215

Number of (weakly) superprimitive binary sequences of length n.

1, 2, 2, 6, 12, 28, 54, 118, 230, 490, 968, 1980, 3978, 8066, 16100, 32494, 64994, 130468, 261000, 523092, 1046292, 2094812, 4189704, 8383732, 16768206, 33545152, 67090578, 134199252, 268399910, 536834026, 1073671504, 2147411556, 4294826718, 8589792856, 17179592372, 34359455674

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

A string x of length n is (strongly) quasiperiodic if there exists a string w of length < n such that x can be exactly covered by (possibly overlapping) occurrences of w in x. For example, 01001010 can be covered by 3 occurrences of 010. A string is (weakly) superprimitive if it is not strongly quasiperiodic.

LINKS

Table of n, a(n) for n=0..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 A216215

EXAMPLE

a(4) = 12 because the 6 strings

0001,

0010,

0011,

0100,

0110,

0111