030. 数字五次幂(Digit fifth powers)

奇怪的是,只有三个数字可以被写成它们各位数的四次方之和:

$$ 1634 = 1^4 + 6^4 + 3^4 + 4^4\\ 8208 = 8^4 + 2^4 + 0^4 + 8^4\\ 9474 = 9^4 + 4^4 + 7^4 + 4^4 $$
因为\(1=1^4\)并不是一个和,所以不包括在内。上面三个数的和\(1634 + 8208 + 9474 = 19316\),求所有可以被写成其各位数的五次方的和的所有数字的和。

分析:假设满足题目要求的数\(n\)\(d\)位数字,易知\(10^{d-1}<n<10^{d}\)。同时考虑到符合条件的数等于其各位数的五次方之和,而对于\(d\)位数其各位数五次方之和最大为\(d\cdot9^5\),即\(n<d\cdot9^5\)。综合以上两个条件,易知\(10^{d-1}<d\cdot9^5\),为了这个不等式,我们对不等式两边求对数得:

$$ d-1<log(d)+5log(9) \Rightarrow d-log(d)<5log(9)+1 $$

求解此不等式,得到\(d<6.59\),由于\(d\)必为整数,则\(d\)最大的取值为6。则根据我们以上的推导,满足条件的数\(n<6\times9^5=354294\),从而可以确定所求数的上界。

为了避免重复0至9的五次方,可以先求出这十个数的五次方并用字典存储,字典的键为这十个数,值为该数的五次方。在计算各位数的五次方之和时,从字典中调取相应数的五次方再相加即可。使用循环分别计算从10到354294的各个数的各位数的五次方之和,满足条件则存储在结果列表中,最后对结果列表求和即为所求。

def main():
    power_dict = {i:i**5 for i in range(0,10)}
    res = []
    for i in range(10,6*9**5):
        sum_of_digits = sum([power_dict[int(x)] for x in str(i)])
        if i == sum_of_digits:
            res.append(i)
    return sum(res)