# Python code for OEIS A265648
# Michael S. Branicky, Aug 17 2021

# A265648		Number of binary strings of length n that are powers of shorter strings, but cannot be written as the concatenation of two or more such strings.
data = [0, 2, 2, 2, 0, 8, 0, 10, 6, 20, 0, 48, 0, 74, 26, 146, 0, 372, 0, 630, 94, 1350, 0, 2864, 0]

from time import time
time0 = time()

# PRECALCULATE ALL POWERS UP TO THIS LENGTH
# CHANGE TO GO HIGHER, DEPENDING ON AVAILABLE RAM
MAXN = 35 

from sympy import divisors
from itertools import product

print("n #pows time")
pows_of_len = [set() for n in range(MAXN+1)]
for n in range(2, MAXN+1):
    for d in divisors(n)[:-1]:
        for b in product("01", repeat=d):
             pows_of_len[n].add("".join(b)*(n//d))
    print(n, len(pows_of_len[n]), time()-time0)
print("PRECALCULATION TIME:", time()-time0)
print()

def is_pow(s):
    global pows_of_len
    return s in pows_of_len[len(s)] 
def is_concat_pows(s, c):
    if len(s) < 2: return False
    if c > 0 and is_pow(s): return True
    for i in range(2, len(s)-1):
        if is_pow(s[:i]) and is_concat_pows(s[i:], c+1): return True
    return False
def ok(s):
    return is_pow(s) and not is_concat_pows(s, 0)
def a(n):
    global pows_of_len
    return 2*sum(ok(s) for s in pows_of_len[n] if s[0] == '0')
print([a(n) for n in range(1, 26)]) # ~~~~

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

alst = []
for n in range(1, MAXN+1):
    an = a(n)
    alst.append(an)
    print(n, a(n), time()-time0, len(str(alst))-2)
    print("   MSB DATA", alst)
    print("   OLD DATA", data)