# Python program for OEIS A226452
# Michael S. Branicky, Jul 09 2022

# A226452 Number of closed binary words of length n.		5
data = [1, 2, 2, 4, 6, 12, 20, 36, 62, 116, 204, 364, 664, 1220, 2240, 4132, 7646, 14244, 26644, 49984, 94132, 177788, 336756, 639720, 1218228, 2325048, 4446776, 8520928, 16356260, 31447436, 60552616, 116753948, 225404486, 435677408, 843029104, 1632918624, 3165936640]

from numba import njit

# (Python)
from numba import njit
@njit
def is_closed(w, n): # is n-digit binary word closed
    if n < 2: return True
    for l in range(1, n):
        mask = (1 << l) - 1
        prefix, suffix = (w & (mask << (n-l))) >> (n-l), w & mask
        if prefix == suffix:
            internal = False
            for j in range(1, n-l):
                result = (suffix << j) ^ ((mask << j) & w)
                if result == 0:
                    internal = True
                    break
            if not internal:
                return True
    return False
@njit
def a(n):
    c = 0
    for b in range(2**(n-1), 2**n):
        c += is_closed(b, n)
    return 2*c if n > 0 else c
print([a(n) for n in range(16)]) # ~~~~


from time import time
time0 = time()

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