Project Euler 21

题目

Amicable numbers

Let \(d(n)\) be defined as the sum of proper divisors of \(n\) (numbers less than \(n\) which divide evenly into \(n\)).

If \(d(a) = b\) and \(d(b) = a\), where \(a \neq b\), then \(a\) and \(b\) are an amicable pair and each of \(a\) and \(b\) are called amicable numbers.

For example, the proper divisors of \(220\) are \(1\), \(2\), \(4\), \(5\), \(10\), \(11\), \(20\), \(22\), \(44\), \(55\) and \(110\); therefore \(d(220) = 284\). The proper divisors of \(284\) are \(1\), \(2\), \(4\), \(71\) and \(142\); so \(d(284) = 220\).

Evaluate the sum of all the amicable numbers under \(10000\).

因数和定理

如果一个正整数\(n\)分解后成为： \[n=\prod_{i=1}^k p_i^{e_i}\] 那么\(n\)的因数的和为： \[\prod_{i=1}^k \dfrac{p_i^{e_i+1}-1}{p_i-1}\] 更一般的，因数的\(k\)次幂的和为 \[\prod_{i=1}^k \dfrac{p_i^{k(e_i+1)}-1}{p_i^k-1}\]

计算因数和的函数将会封装在tools中并且以divisor_sigma(n,k=None)的方式调用。

解决方案

可以直接通过因数和定理，先将所有\(10000\)以下的数进行分解，然后计算出真因数的值。

最后直接判断两对数是否满足亲和数的条件。

计算\(1\sim n\)中的所有因数和也可以通过欧拉筛加速计算。

代码

from tools import divisors_sigma

N = 10000
d = [0 for _ in range(N)]
for i in range(1, N):
    d[i] = divisors_sigma(i)-i
ans = 0
for i in range(1, N):
    if N > d[i] > i == d[d[i]]:
        ans += i + d[i]
print(ans)