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

Author

Jeffrey Shallit, Mar 13 2013

Keywords

• nonn

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.

Examples

			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.
		

Links

• 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

Crossrefs

Cf. A216214.

Programs

C

See Links section.

Extensions

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