# Python program for OEIS A370410 (using bitwise operations)
# Michael S. Branicky, Feb 18 2024

# A370410 Number of length-n binary strings that are the concatenation of two nonempty palindromes.

# data from OP, JS
data = [0, 4, 6, 14, 26, 48, 86, 148, 232, 400, 622, 982, 1514, 2440, 3482, 5680, 8162, 12932, 18398, 29146]


from numba import njit

@njit
def p(w, n):
    if w == 0: return 1
    mask1, mask2 = 1, 1<<(n-1)
    for i in range(n>>1):
        if ((w&mask1)>0) != ((w&mask2)>0):
            return 0
        mask1 <<= 1
        mask2 >>= 1
    return 1

@njit 
def c(w, n): 
    for i in range(1, n):
        if p(w&((1<<i)-1), i) and p(w>>i, n-i):
            return 1
    return 0

@njit
def a(n):
    ans = 0 
    for w in range(2**(n-1), 2**n):
        if c(w, n):
            ans += 1
    return 2*ans

print([a(n) for n in range(1, 21)])

print(data)
assert data == [a(n) for n in range(1, 21)]

from time import time
time0 = time()

alst = []
for n in range(1, 1001):
    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)