오일러 프로젝트 23 번

오일러 프로젝트 23 번

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다.
따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다.
두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=23

1~11의 자연수는 두 초과수의 합으로 나타낼 수 없는 값이다. 12~28123 내의 모든 초과수를 찾아서 세트로 만든 다음, 12~28123 사이의 임의의 n에 대해서 초과수 i를 골라서 (n – i)가 초과수에 있는지 찾는다. 그러면 이 수는 두 초과수의 합인 수이다. 이 조건을 만족하지 않는 수의 합을 구하면 된다.

ef sumOfDivisors(n):
    k = 2
    s = 1
    l = int(n ** 0.5)
    while k <= l:
        if n % k == 0:
            s += k + n // k
        k += 1
    if l*l == n:
        return s - l
    return s

def isOverNum(n):
    return sumOfDivisors(n) > n * 2

def main():
    overnums = set([x for x in range(12, 28123) if isOverNum(x)])

    def test(n):
        for i in overnums:
            if (n - i) in overnums:
                return True
        return False

    result = []
    for i in range(12, 28123):
        if not test(i):
            result.append(i)
    ans = sum(list(range(1, 12)) + result)
    print(ans)

%time main()

#342289245
#Wall time: 3.43 s