项目欧拉问题23 非丰富数之和
完美数是指其所有真因数(不包括本身)的和恰好等于该数本身的正整数。例如,28的真因子之和为1 + 2 + 4 + 7 + 14 = 28,这意味着28是一个完美数。
如果一个数n的真因数之和小于n,则称其为不足数(deficient);如果其真因数之和大于n,则称其为过剩数(abundant)。
作为最小过剩数,12的真因数之和为1 + 2 + 3 + 4 + 6 = 16,可以写成两个过剩数之和的最小数字为24。经过数学分析,可以证明所有大于28123的整数都可以被写成两个过剩数之和。但是,即使已知不能表示为两个过剩数之和的最大数小于此限制,也无法通过分析进一步减少此上限。
找出所有无法被写成两个过剩数之和的正整数之和。
以下是我的代码,运行时间为25秒以解决此问题。
import time
def check_abundant(n):
s=0
for i in range(1,n/2+1):
if n%i==0:
s+=i
if n<s:
return True
else:
return False
start = time.time()
check=[None]*28123
check[12]=True
for i in range(1,12):
check[i]=False
total=0
can=0
for i in range(1,28123+1):
canbe=False
'''
if i<24:
total+=i
if i==24:
total+=0
'''
for j in range(1,i/2+1):
if check[j]==None:
check[j]=check_abundant(j)
if check[i-j]==None:
check[i-j]=check_abundant(i-j)
if check[j]==True and check[i-j]==True:
canbe=True
break
if canbe==False:
total+=i
elapsed = (time.time() - start)
print "%s found in %s seconds" % (total,elapsed)
但我在这里有一个棘手的问题,因为描述中说,“24是可以写成两个丰富数字之和的最小数字”,对我来说,这也意味着“1-23不能被写成两个丰富数字之和”,因为它们“比24小而且它们是正整数”。
这就是问题所在。在我的代码中,如果我直接将1-23添加到最终输出中(因为它们显然是总和的一部分),我将得到4180147,这是4179871+sum(range(1,24))。如果我像其他数字一样检查这些数字,我会得到正确答案4179871。
据我所见,描述和我的代码之间存在冲突。如果4179871是正确答案,那么“1-23是可以写成两个丰富数字之和的整数”,但根据描述,实际上它们不行(24是最小的)。
这个问题几乎把我逼疯了,有人能帮忙吗?非常感谢!