from time import perf_counter as clock

def eureka4(ndigits):
    """ Calculate eureka numbers with ndigits digits"""
    # b is a table with ndigits rows for every position in the number
    #    and 10 columns for the digits
    #    b[pos][d] is the difference between d^(pos+1) and d*10^(ndigits-(pos+1))
    # for a solution the cumulative difference should be zero.
    # As the decimal magnitudes for digits are largest at the left of a number and the 
    # power contributions the largest at the right of the number, the differences are 
    # very negative at the left and very positive at the right. Moreover the ranges of
    # the differences are the highest at the left and the right and the lowest in the 
    # middle. For a branch and bound strategy is works well to process the numbers 
    # in the order of the range of the differences per position.
    b = [[x ** (j+1) - x * 10 ** (ndigits - (j+1)) for x in range(10)]
         for j in range(ndigits)]
    smin = [min(bi) for bi in b]  # min value for every row of b
    smax = [max(bi) for bi in b]  # max value for every row of b
    # pers is a permutation of [0, ndigits) with key: the range of the numbers of row b
    perm = sorted(range(ndigits), key=lambda j: smax[j]-smin[j], reverse=True)
    # scmin and scmax are the min and max contributions possible for the remaining digits
    # in the permuted order
    scmin = [sum(smin[perm[i]] for i in range(j+1, ndigits)) for j in range(ndigits)]
    scmax = [sum(smax[perm[i]] for i in range(j+1, ndigits)) for j in range(ndigits)]
    # now permute b, so that it is not necessary every time in branch
    b = [b[j] for j in perm]

    def branch():
        # search for solutions. Add positions in the order of the permutation,
        # so that the (permuted) positions with the largest ranges come first
        # the lower bound for the current state: current + scmin[pos] should be <= 0
        # the upper bound for the current state: current + scmax[pos] should be >= 0
        Q = [(0, 0, [])]
        while Q:
            pos, sofar, num = Q.pop()
            x0 = 1 if perm[pos] == 0 else 0
            for x in range(x0, 10):
                current = sofar + b[pos][x]
                if scmin[pos] <= -current <= scmax[pos]:
                    if pos == ndigits-1:
                        yield num + [x]
                    else:
                        Q.append((pos+1, current, num + [x]))

    for num in branch():
        decimal = sum(d*10**(ndigits-perm[i]-1) for i, d in enumerate(num))
        print(decimal)

t0 = clock()
# solutions are only possible for a number of digits up to 22
# it turns out that the highest solution has 20 digits
for ndigits in range(1, 10):
    eureka4(ndigits)

"""
PyPy
trying 1 digits
1 1.22 msec
2 1.45 msec
3 1.64 msec
4 1.82 msec
5 1.96 msec
6 2.15 msec
7 2.34 msec
8 2.49 msec
9 2.62 msec
elapsed time: 2.72 msec
trying 2 digits
89 3.17 msec
elapsed time: 535 usec
trying 3 digits
518 3.9 msec
598 4.05 msec
135 4.25 msec
175 4.4 msec
elapsed time: 1 msec
trying 4 digits
2427 5.5 msec
1676 5.74 msec
1306 5.97 msec
elapsed time: 1.7 msec
trying 5 digits
elapsed time: 6.57 msec
trying 6 digits
elapsed time: 14.4 msec
trying 7 digits
2646798 38.7 msec
elapsed time: 11.1 msec
trying 8 digits
elapsed time: 4.4 msec
trying 9 digits
elapsed time: 1.77 msec
trying 10 digits
elapsed time: 39 msec
trying 11 digits
elapsed time: 39.1 msec
trying 12 digits
elapsed time: 72.9 msec
trying 13 digits
elapsed time: 130 msec
trying 14 digits
elapsed time: 491 msec
trying 15 digits
elapsed time: 994 msec
trying 16 digits
elapsed time: 4.27 sec
trying 17 digits
elapsed time: 10.6 sec
trying 18 digits
elapsed time: 50.7 sec
trying 19 digits
elapsed time: 138 sec
trying 20 digits
12157692622039623539 531 sec
elapsed time: 505 sec
trying 21 digits
elapsed time: 1.41 ksec
trying 22 digits
elapsed time: 516 sec
trying 23 digits
elapsed time: 3 msec
trying 24 digits
elapsed time: 14.5 msec
Total time 2636 secs
"""