Certain Power of Sum of Digits of N == N (running too slowly)

Question

I'm trying to write a Python script that finds all integers (N) where a certain power of the sum of the digits of N is equal to N. For example, N=81 qualifies, because 8 + 1 = 9, and a certain power of 9 (namely 2) = 81.

The ranges I chose are arbitrary. My script works but it is very, very slow. Ideally, I'd want to find the first 30 such integers in about 6000ms.

My first solution:

def powerOfSum1():
    listOfN = []
    arange = [a for a in range(11, 1000000)] #range of potential Ns
    prange = [a for a in range(2, 6)] # a range for the powers to calculate
    for num in arange:
        sumOfDigits = sum(map(int, str(num)))
        powersOfSum = [sumOfDigits**p for p in prange]
        if num in powersOfSum:
            listOfN.append(num)
    return listOfN

In my second solution, I tried storing all the powers for each sumOfDigits, but that did not improve the performance much.

def powerOfSum2():
    listOfN = []
    powers= {}
    for num in range(11, 1000000):
        sumOfDigits = sum(map(int, str(num)))
        summ = str(sumOfDigits)
        if summ in powers:
            if num in powers[summ]:
                listOfN.append(num)
        else:
            powersOfSum = [sumOfDigits**p for p in range(2,6)]
            powers[summ] = powersOfSum
            if num in powers[summ]:
                listOfN.append(num)
    return listOfN

I haven't studied data structures and algorithms yet, so I'd appreciate any pointers on making this script more efficient.

Answer 1

Update: I've discovered this is a Project Euler problem (#119) and I've found basically the same solution already documented: http://www.mathblog.dk/project-euler-119-sum-of-digits-raised-power/

I'm not sure if I am over simplifying but just iterating over the powers for a range of numbers seems pretty quick. You can't guarantee the order so calculate more than you need and then sort and take the top 30. I can't prove I've got them all but I've tested base up to 500 and exp up to 50 and it returns the same top 30. It should be noted the OP only tested exponents up to 5, which limits the number of results significantly:

def powerOfSum():
    listOfN = []
    for base in range(2, 100):
        num = base
        for _ in range(2, 10):
            num *= base
            if sum(map(int, str(num))) == base:
                listOfN.append(num)
    return sorted(listOfN)[:30]
powerOfSum()

Output

[81,
 512,
 2401,
 4913,
 5832,
 17576,
 19683,
 234256,
 390625,
 614656,
 1679616,
 17210368,
 34012224,
 52521875,
 60466176,
 205962976,
 612220032,
 8303765625,
 10460353203,
 24794911296,
 27512614111,
 52523350144,
 68719476736,
 271818611107,
 1174711139837,
 2207984167552,
 6722988818432,
 20047612231936,
 72301961339136,
 248155780267521]

Running timeit on it (including the sort) I get:

100 loops, best of 3: 1.37 ms per loop