N == N的数字和的某些幂(运行太慢)

Question

我正在尝试编写一个Python脚本,找到所有整数(N),其中N的数字之和的某个幂等于N.例如,N = 81符合条件,因为8 + 1 = 9,并且a某个9的幂(即2)= 81.

我选择的范围是任意的.我的脚本有效,但非常非常慢.理想情况下,我想在大约6000ms内找到前30个这样的整数.

我的第一个解答:

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

在我的第二个解决方案中,我尝试为每个sumOfDigits存储所有权限,但这并没有提高性能.

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

我还没有研究过数据结构和算法,所以我很欣赏任何关于使这个脚本更有效的指针.

Answer 1

更新：我发现这是一个 Project Euler 问题（#119），并且我发现基本上已经记录了相同的解决方案：http://www.mathblog.dk/project-euler-119-sum-of-digits-升功率/

我不确定我是否过度简化，但只是迭代一系列数字的幂似乎很快。你不能保证顺序，所以计算出比你需要的更多的东西，然后排序并取前 30 个。我无法证明我已经得到了全部，但我已经测试了base最多 500 个和exp最多 50 个，它返回相同的结果top 30. 应该注意的是，OP 只测试了最多 5 的指数，这极大地限制了结果的数量：

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

输出

[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]

运行timeit它（包括排序）我得到：

100 loops, best of 3: 1.37 ms per loop