# Python program for OEIS A348429
# Michael S. Branicky, Oct 19 2021

# A348429		Perfect powers m^k, m >= 1, k >= 2 such that m and m^k both are palindromes.		0
data = [1, 4, 8, 9, 121, 343, 484, 1331, 10201, 12321, 14641, 40804, 44944, 1002001, 1030301, 1234321, 1367631, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 1003003001, 10000200001, 10221412201, 12102420121, 12345654321, 40000800004]

from itertools import product
def pals(maxdigits, base=10): # all d-digit palindromes
    digits = "".join(str(i) for i in range(base))
    for d in range(1, maxdigits+1):
        for p in product(digits, repeat=d//2):
            if d > 1 and p[0] == "0": continue
            left = "".join(p); right = left[::-1]
            for mid in [[""], digits][d%2]: yield int(left + mid + right)

# (Python)
def ispal(n): s = str(n); return s == s[::-1]
def aupto(limit):
    aset, m, mm = {1}, 2, 4
    palsgen = pals(len(str(limit)))
    m = next(palsgen) # generate 0
    m = next(palsgen) # generate 1
    while mm <= limit:
        m = next(palsgen)
        mm = m*m
        mk = mm
        while mk <= limit:
            if ispal(mk):
                aset.add(mk)
            mk *= m
    return sorted(aset)
print(aupto(10**11)) # ~~~~

print(data)
assert data == aupto(10**11)
print()

from time import time
time0 = time()

for e in range(11, 1001):
    ans = aupto(10**e)
    with open('b348429.'+str(e)+'.txt', 'w') as bfile:
        for n, an in enumerate(ans, start=1):
            bfile.write(f"{n} {an}\n")
    print(e, len(ans), time()-time0, ans)