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\ne 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{\displaystyle \frac{p_i^{e_i+1}-1}{p_i-1}}$$ 更一般的，因数的 $k$ 次幂的和为 $$\prod _{i=1}^k{\displaystyle \frac{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)