友愛数

Project Euler 21

$d(n)$ を $n$ の真の約数の和とする（$n$ の真の約数とは、$n$ 以外で $n$ を割り切る数とする）。
$d(a) = b$ であり $d(b) = a$（ただし $a\neq b$）を満たすとき、$a$ と $b$ を友愛数と呼ぶ。

たとえば $220$ の真の約数は、$1, 2, 4, 5, 10, 11, 20, 22, 44, 55$ そして $110$ である。それゆえ $d(220) = 284$ となる。また、$284$ の真の約数は、$1, 2, 4, 71, 142$ であり、$d(284) = 220$ である。

$1000$ 未満の友愛数の和を求めよ。

---

先日定義した素因数分解の関数 factorize を利用し、約数取得用の関数を作成する。

def __divisor__(p, q):
    x = []
    for i in range(q+1):
        x.append(p**i)
    return x


def divisor(n, proper=False):
    xs = factorize(n)
    xl = __divisor__(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        xl = [x*y for x in __divisor__(p, q) for y in xl]
    if proper is True:
        xl.remove(n)
    return sorted(xl)

divisor の引数 proper に True を与えると、真の約数（自分自身を含まない約数）を取得できるようにしてある。
これを用いて友愛数をリスト化し、その後、リスト内の数値を加算する。

import time

start = time.clock()

N = 10000
amicable_nums = []


for i in range(1, N+1):
    d = sum(divisor(i, proper=True))
    if d <= i:
        continue
    if sum(divisor(d, proper=True)) == i:
        amicable_nums.extend([i, d])

print(int(sum(amicable_nums)))
print("processing time : ", time.clock() - start)