023. 非过剩数之和(Non-abundant sums)

完美数是指其所有真因子的和等于其自身的数。例如,28的所有真因子的和为:

$$ 1+2+4+7+14=28 $$
这意味着28是一个完美数。如果一个数的真因子的和小于该数自身,称其为缺陷数;如果大于该数自身,则称其为过剩数。可以发现12是最小的过剩数,而24是最小的可以写为两个过剩数之和的数。通过数学分析可以发现,所有大于28123的数都可以写成两个过剩数之和。然而,我们无法通过数学分析进一步降低这个上界,尽管我们知道最大的不能写为两个过剩数之和的数小于这一上界。求所有无法写为两个过剩数之和的所有自然数的和。

分析:二十一题中提到了两种计算真因子之和的思路并采用了第二种思路,这里用第一种思路再实现一次。对于特定自然数,我们只要计算其真因子之和,如果真因子之和大于这个数本身,则它是一个过剩数。题目要求上界以下所有不能被表示两个过剩数之和的自然数之和,一个效率较高的思路是:从一至上界进行遍历,判断某个数是否是过剩数,如果是则加入到过剩数集合中。考虑到一个自然数只有可能被表示成两个比它小的过剩数之和,因此我们可以用该数减去已经获得的过剩数集合中的每一个数,如果所得的差中没有一个数是过剩数,则这个数不可能被表示成为两个过剩数之和。对此类数依次累加,所得总和即为题目所求。代码实现如下:

# time cost = 798 ms ± 1.93 ms

def sigma(n):
    res = 0
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            res += (i + n//i) if i**2 != n else i
    return res-n

def main():
    limit = 28123
    res,abn = 0,set()
    for i in range(1,limit+1):
        if sigma(i)>i:
            abn.add(i)
        if not any((i-x in abn) for x in abn):
            res += i
    return res