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

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
and their complements are the only weakly superprimitive strings of length 4.

Prog

(C) See Links section.

Crossrefs

Cf. A216214.

Sequence in context: A035615 A115962 A019311 * A052994 A088219 A027375

Adjacent sequences: A216212 A216213 A216214 * A216216 A216217 A216218

Keyword

nonn

Author

Jeffrey Shallit, Mar 13 2013

Extensions

a(17)-a(35) from Rémy Sigrist, Jan 09 2019

Status

approved