非過剰数の和

Project Euler 23

完全数とは、当該数とその数の真の約数の和が一致する数のことである。例えば 28 の約数の和 1 + 2 + 4 + 7 + 14 = 28 となるため、28 は完全数である。

真の約数の和がその数に満たない数を不足数といい、超過する数を過剰数という。

12 は 1 + 2 + 3 + 4 + 6 = 16 となるため最小の超過数である。よって、2 つの過剰数の和のうち最小の数は 24 となる。数学的に 28123 より大きな整数は、2 つの過剰数の和で表現できることが証明されている。 しかし、2 つの過剰数の和で表すことのできない最大の数がこの上限値よりも小さいことは判明しているが、この上限値を減らすことができていない。

2 つの過剰数の和で表現できない正の整数の和を計算せよ。

---

28123 以上の整数はすべて過剰数の和で表現できるため、当該値までのリストを作成し、過剰数を事前に算出する。 なお、divisor は与えられた数の約数をリスト化する。

N = 28123

def create_list():
    l = [0 for i in range(N)]
    for i in range(1, N):
        # 過剰数の場合、リストの該当番目を True にする。
        if i < sum(divisor(i, True)):
            l[i] = 1
    return l

ここで作成したリストをもとに、与えられた数が過剰数であるか否かをチェックする。
まず、与えられた整数 $n$ に対して、最小過剰数 $12$ から $n/2$ までの過剰数を確認する。この範囲内で過剰数 $i$ が存在する場合、$n-i$ が過剰数か否かをリストをもとに確認する。
なお、チェックの上限が $n/2$ となっているのは、$n/2$ より大きな2つの数の和は $n$ を超過するためである。

MIN_ABUNDANT = 12

def check(n, l):
    for i in range(MIN_ABUNDANT, int(n/2)+1):
        if l[i] == 0:
            continue
        if l[n-i] == 1:
            return True
    return False

これらを組み合わせて、非過剰数の和を算出する。なお、23 までは 2 つの過剰数の和で表現できないことが判明しているため、予め総和を計算しておく。

ans = sum([i for i in range(MIN_ABUNDANT*2)])
l = create_list()
for n in range(MIN_ABUNDANT*2, N):
    if check(n, l) is False:
        ans += n
print("Answer = ", ans)
print("processing time : ", time.clock() - start)