欧拉计划23题:棘手的冲突

3

项目欧拉问题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是最小的)。
这个问题几乎把我逼疯了,有人能帮忙吗?非常感谢!

1
这可能更适合在Project Euler论坛上提问。请访问http://forum.projecteuler.net/viewtopic.php?f=50&t=985&start=30&hilit=problem+023。 - sfjac
1个回答

1

您的代码已经将1到23的数字添加到total中。

如果您修改程序以打印出添加了哪些数字:

if canbe==False:
    print 'added ' + str(i)
    total+=i

该程序将会打印出以下内容:
added 1
added 2
added 3
added 4
added 5
added 6
added 7
added 8
added 9
added 10
added 11
added 12
added 13
added 14
added 15
added 16
added 17
added 18
added 19
added 20
added 21
added 22
added 23
added 25
...

您会发现数字1到23已经被添加到total中,因此您不需要自己添加。


1
太棒了!非常感谢,我看到了我的代码出了什么问题,太明显了,我忘记了“if i>24:”这个条件。我简直不敢相信我花了几个小时在上面 :b - 李手指头

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接