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.

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

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 A361298 A091915

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