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