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

%I #34 Oct 09 2023 09:01:10

%S 1,2,2,6,12,28,54,118,230,490,968,1980,3978,8066,16100,32494,64994,

%T 130468,261000,523092,1046292,2094812,4189704,8383732,16768206,

%U 33545152,67090578,134199252,268399910,536834026,1073671504,2147411556,4294826718,8589792856,17179592372,34359455674

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

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

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

%H Rémy Sigrist, <a href="/A216215/a216215.txt">C program for A216215</a>

%e a(4) = 12 because the 6 strings

%e 0001,

%e 0010,

%e 0011,

%e 0100,

%e 0110,

%e 0111

%e and their complements are the only weakly superprimitive strings of length 4.

%o (C) See Links section.

%Y Cf. A216214.

%K nonn

%O 0,2

%A _Jeffrey Shallit_, Mar 13 2013

%E a(17)-a(35) from _Rémy Sigrist_, Jan 09 2019