# Python code for OEIS A323446
# Michael S. Branicky, Dec 07 2021

# 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.
data = [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]

# with 64-bit int's, njit can be used up to n=62 without overflow issues

# On Google Colab, gets through a(25) in ~1s, a(30) in ~70s, a(40) in ~13.5h

# (Python)
from numba import njit
from itertools import product

@njit
def issquare(w, n):
    if n == 0 or n%2 == 1: return False
    mask = (1 << n//2) - 1
    return ((w & (mask << n//2)) >> n//2) == (w & mask)

@njit
def c(k, n):
    fullmask = (1 << n) -1
    for leny in range(n-2, 0, -2):
        zmask = (1 << (n - leny)) - 1 
        for offset in range(1, n-leny):
            xmask = fullmask ^ (fullmask >> offset)
            zmask >>= 1 
            if issquare(((k & xmask) >> leny) + (k & zmask), n-leny):
                return False
    return not issquare(k, n)

@njit
def a(n):
    count = 0
    for k in range(2**(n-1), 2**n):
        if c(k, n):
            count += 1
    return 2*count
print([a(n) for n in range(1, 25)]) # ~~~~
print(data)
print()

from time import time
time0 = time()
alst = []
for n in range(1, 41):
    an = a(n)
    alst.append(an)
    print(n, an, time()-time0, flush=True)
    print("   ", alst, flush=True)
    print("   ", data, flush=True)