# Python program for OEIS A229614
# Michael S. Branicky, Nov 11 2021

# A229614		Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 2.		3
data = [1, 2, 4, 8, 16, 32, 56, 104, 178, 314, 536, 930, 1558, 2666, 4482, 7574, 12686, 21360, 35812, 60152, 100812, 169122, 283498, 475356, 796292, 1334558, 2235888, 3746534, 6276048, 10515080, 17614726, 29510362, 49434792, 82815016, 138729368, 232399846, 389306052]

# (Python)
from numba import njit
@njit
def sf3(k, n):  # binary number k with n bits has no square xx with |x| > 2 
    for l in range(3, n//2 + 1):
        mask1 = ((1 << l) - 1) << l
        mask2 = (1 << l) - 1
        for i in range(n-2*l+1):
            if ((mask1&k) >> l) == mask2&k:
                return False
            mask1 <<= 1
            mask2 <<= 1
    return True
@njit       
def a(n):
    if n == 0: return 1
    c = 0
    for k in range(2**(n-1), 2**n):
        if sf3(k, n):
            c += 1
    return 2*c
print([a(n) for n in range(30)])

print(data)

from time import time
time0 = time()

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