欧拉计划23题回答错误

3
我刚刚完成了对欧拉计划第23题的解决方案,该问题陈述如下:
完全数是指其真约数之和恰好等于该数本身的数。例如,28的真约数和为1+2+4+7+14=28,因此28是一个完美数。
如果一个数n的真约数之和小于n,则称其为不足数;如果这个总和超过n,则称其为丰富数。
由于12是最小的丰富数,1 + 2 + 3 + 4 + 6 = 16,可以写成两个丰富数之和的最小数字是24。通过数学分析,可以证明所有大于28123的整数都可以写成两个丰富数之和。但是,即使已知不能将无法表示为两个丰富数之和的最大数字小于此限制,但无法通过分析进一步缩小此上限。
请找出所有不能写成两个丰富数之和的正整数的总和。
以下是我的解决方案:
from math import sqrt
def divisors(n):
    for i in range(2, 1 + int(sqrt(n))):
        if n % i == 0:
            yield i
            yield n / i

def is_abundant(n):
    return 1 + sum(divisors(n)) > n

abundants = [x for x in range(1, 28123 + 1) if is_abundant(x)]
abundants_set = set(abundants)

def is_abundant_sum(n):
   for i in abundants:
       if i > n:  # assume "abundants" is ordered
         return False
       if (n - i) in abundants_set:
           return True
   return False

sum_of_non_abundants = sum(x for x in range(1, 28123 + 1) if not is_abundant_sum(x))
print(sum_of_non_abundants)

我的答案是:3906313

代码解释:

divisors生成器基本上返回一个整数的所有非平凡因子,但不能保证顺序。它遍历从1到n的平方根,并产生除数和商。下一个函数is_abundant实际上检查n的因子之和是否小于n,如果是则返回False,否则返回True。接下来的列表abundants保存了从1到28123的所有过剩数,而abundants_setabundants类似,但它是一个集合而不是列表。下一个函数是is_abundant_sum,它基本上检查给定的总和本身是否丰富,最后打印出不是is_abundant_sum的数字的总和。

我的代码有什么问题?哪里出错了?

任何帮助都将不胜感激。


你的问题在于你的除数函数。 - Padraic Cunningham
@PadraicCunningham 什么问题? - Mohammad Areeb Siddiqui
如果您在因子函数中添加总和并返回,然后只调用该函数,忘记is_abundant。 - Padraic Cunningham
1个回答

2
生成器会将 f**2 的因子 f 计算两次。这个漏洞影响了计算出的过剩数列表。

那我应该把得到的因子数量减半吗? :P - Mohammad Areeb Siddiqui
最简单的解决方法是仅在 n / i 大于 i 时产生结果。 - David Eisenstat
@DavidEisenstat 即使我应用了你的修复,我仍然得到了4179871,这仍然是不正确的。 :/ - Mohammad Areeb Siddiqui
@MohammadAreebSiddiqui 因为 i 小于或等于 sqrt(n),我们知道 i**2 <= n,因此 i <= n/i。除非 i < n/i,否则第二个 yield 语句会重复因子 i - David Eisenstat
@DavidEisenstat 即使我应用了你的修复,我仍然得到了4179871,这仍然是不正确的。 :/ - Mohammad Areeb Siddiqui
显示剩余7条评论

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