Project Euler 023を解いてみる。「非過剰数和」

Project Euler 023

023

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである.
たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である.
真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.
12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である.
よって2つの過剰数の和で書ける最少の数は24である.
数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている.
2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.
2つの過剰数の和で書き表せない正の整数の総和を求めよ.

->次の問題

考え方

[1~28123までの過剰数]を列挙、ループを使って[2つの過剰数の和の集合]を作成します。
[1~28123の自然数の集合]から[過剰数の和の集合]を減算することで[非過剰数和の集合]を得ます。

コード

euler023.py

def main():
    limit = 28123
    # 1~28123の自然数のset
    all_num_set = set(range(1, limit + 1))
    # 過剰数のlist
    excess_numbers = [i for i in range(1, limit + 1) if is_excess_number(i)]

    # 過剰数の和のsetを作成。重複する要素はsetによって自動で除去される。
    excess_sum_set = set()
    for excessA in excess_numbers:
        # 12+20と20+12のように入れ替えてもは結果は同じなので、
        # 重複しないようにexcessA以上の数字のみループに使用。
        for excessB in excess_numbers[excess_numbers.index(excessA):]:
            sum_num = excessA + excessB
            # 和が28123より大きければループを抜ける
            if sum_num > limit:
                break
            excess_sum_set.add(sum_num)

    # setの差分で[全ての数字の集合]から[過剰数の和の集合]を除外
    answer_set = all_num_set - excess_sum_set
    # 合計して答え
    print(sum(answer_set))


def is_excess_number(n):
    """
    過剰数か否かを判定する関数
    Args:
        n: 自然数
    Returns:
        bool: 過剰数ならTrue,それ以外ならFalse
    """
    # 約数1は必ず含まれる
    sum_divisors = 1
    # 探索範囲は2~√n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            sum_divisors += i
            # nが2乗数でなければn/iも約数の和に追加
            if i ** 2 != n:
                sum_divisors += n // I
        # 約数の和がnより大きければ過剰数
        # ループの中でも外でも時間はあまり変わらなかった
        if sum_divisors > n:
            return True
    return False


if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')

paizaにて実行
結果 4179871 1.5287187099456787 sec