|
| |
|
|
A323446
|
|
Number of binary strings w of length n that cannot be written in the form xyz, with x,z both nonempty and xz a square.
|
|
1
|
|
|
|
2, 2, 4, 6, 8, 12, 16, 26, 36, 70, 104, 220, 372, 758, 1408, 2874, 5472, 11056, 21696, 43546, 86060, 172514, 343068, 686888, 1369484, 2740080, 5471464, 10945900, 21872228, 43749868, 87460604, 174931610, 349777232, 699576604, 1398973652, 2797992934, 5595603056, 11191292048, 22381785572, 44763754898
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
A square is a nonempty block of the form XX.
|
|
|
LINKS
|
Table of n, a(n) for n=1..40.
Michael S. Branicky, Python program
|
|
|
EXAMPLE
|
For n = 6 the 12 solutions are {000001, 000011, 000111, 001011, 001111, 011111} and their complements.
|
|
|
PROG
|
(Python) # see links for a faster, bit-based version
from itertools import product
def issquare(w):
if len(w) == 0 or len(w)%2 == 1: return False
return w[:len(w)//2] == w[len(w)//2:]
def c(b):
for leny in range(len(b)-2, 0, -2):
for offset in range(1, len(b)-leny):
if issquare(b[:offset] + b[offset+leny:]):
return False
return not issquare(b)
def a(n):
return 2*sum(1 for b in product("01", repeat=n-1) if c("1"+"".join(b)))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Dec 07 2021
|
|
|
CROSSREFS
|
Sequence in context: A080054 A108494 A078578 * A018129 A091915 A123862
Adjacent sequences: A323443 A323444 A323445 * A323447 A323448 A323449
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Jeffrey Shallit, Jan 15 2019
|
|
|
EXTENSIONS
|
a(21)-a(33) from Lars Blomberg, Jan 26 2019
a(32)-a(33) corrected and a(34)-a(40) from Michael S. Branicky, Dec 07 2021
|
|
|
STATUS
|
approved
|
| |
|
|
