seq002

import heapq
import math

def appr_lim(n):
    l10 = math.log(10.0)
    x = 4 * n * math.log(n)
    for _ in range(4):
        x = (l10 + n * (math.log(9 * x) - 1)) / (l10 - n / x)
    k = math.ceil(x)
    #print("appr_lim", n, k)
    assert (k > n)
    assert (10**k > 10 * (9*k)**n)
    return k

def sum_digits(n):
    cnt = 0
    res = 0
    while n:
        res += n % 10
        cnt += 1
        n //= 10

    return (res, cnt)

h = [(4, 2, 2)]
lims = [1, 2, appr_lim(2)]
seq = []

def step():
    v = heapq.heappop(h)
    x = v[0]
    n = v[1]
    a = v[2]

    sd = sum_digits(x)
    if (sd[0] == a):
        print(v)
        seq.append(x)
    if (1 * sd[1] < lims[n]):
        heapq.heappush(h, ((a + 1)**n, n, a+1))
    if (a == 2):
        heapq.heappush(h, (2**(n+1), n+1, 2))
        lims.append(appr_lim(n + 1))

while (len(seq) < 100):
    step()