【Project Euler】Problem 21: 友愛数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 21. 友愛数

原文 Problem 21: Amicable numbers

問題の要約：10000未満の友愛数の合計を求めよ

友愛数(Wikipedia)に詳しい説明がありますが、「自分自身を除いた約数の和が、互いに他方と等しくなるような数をいう」とのこと。まず「自分自身を除いた約数（proper divisors）の和」を求める関数sumpdivを作ります。220と284が友愛数になっていることを確認。

from sympy import divisors
# sum of the proper divisors
def sumpdiv(n):
  return sum(sympy.divisors(n))-n

print(sumpdiv(220),sumpdiv(284))
#284 220

これをもとに10000未満の友愛数を探します。

spdlist = [0]    # store sum of the proper divisors of n
ans = 0
for n in range(1,10000):
  spd = sumpdiv(n)
  spdlist.append(spd)
  if spd < n and spdlist[spd] == n:    # check if amicable number
    print(n, spd)
    ans += n+spd
print(f"Answer: {ans}")