119. 数字和的幂(Digit power sum)

\(512\)是一个有趣的数,因为它等于其各位数字之和的整数幂:\(5+1+2=8\),而\(8^3=512\)。还有一个拥有同样性质的数字是\(614656=28^4\)

\(a_n\)为这类数字中的第\(n\)个,并且约定一个数至少需要两位数字才有各位数字和。我们已知\(a_2=512\)以及\(a_{10}=614656\),求\(a_{30}\)

分析:这是一道比较简单的题目,有两个思路:第一个思路是对于一个数\(n\),计算它的各位数字之和\(ds(n)\),然后看\(n\)是否可以表示成为\(ds(n)\)的整数次幂,一直找到第三十个符合要求的\(n\)即为题目所求。由于我们找的数字可能非常大,但这种方法只能通过每次累加一的方式更新\(n\),所以效率会比较低,不能在规定时间内找到答案。

第二种思路则反过来思考,确定一个底数\(b\)和一个指数\(p\),计算\(b^p\),然后判断\(ds(b^p)\)是否等于\(b\),如果等于则是一个符合要求的数。这种方法筛选出来的数不是按顺序排列的,所以我们筛选出来的符合要求的数字要大于三十个,然后再对这些数字升序排列,找到其中第三十个就可以了。这里\(b\)\(p\)的取值范围需要自己尝试,我发现给定范围\(1< b<100,1< p<10\)就可以找到题目要求的数。代码如下:

# time cost = 2.68 ms ± 16.7 µs per

def main(k=30):
    arr = []
    for b in range(2,100):
        for p in range(2,10):
            n = b ** p
            if n > 10:
                ds = sum([int(x) for x in str(n)])
                if ds == b:
                    arr.append(n)
    return sorted(arr)[k-1]