0119 数字和的幂
* * * *
拉格朗日计划
* * * *
数字和的幂

512是个有趣的数,因为它等于其各位数字和的幂:$512=(5+1+2)^3$。另一个拥有同样性质的数是$614656=(6+1+4+5+6)^3$。

从两位数开始考察,记$a_n$是第n个这样的数,则$a_2=512$,$a_{10}=61456$。

求$a_{30}$。

本题难度:



解答

n位数共有$10^n-10^{n-1}$个,相比之下其各位数字之和最大不超过9n,总数要小得多。

因此只需在一定范围内(以下选择的是200)遍历可能的数字和a,并计算其幂$a, a^2,\ldots, a^k$直到$a^{k+1}$超过$a$位为止,并检查这些幂的数字和是否等于$a$。

最后将结果排序并选择其中第30个数即得$248155780267521$。

def p(a,b):
  if b < 10:
      return a**b
  else:
      c=p(a,b/2)
      return c*c*a if a%2 else c*c

r=[]
for n in range(2,200):
  k=1
  m=n
  s=str(m)
  while len(s) <=n:
      if len(s)>1 and sum(int(i) for i in s)==n:
          r.append(m)
      k+=1
      m=p(n,k)
      s=str(m)
r.sort()
print r[29],r[1],r[9]