# 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)