오일러 프로젝트 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

접근

문제에서 제시했듯이 가장 작은 초과수가 12이므로, 24~28123 사이의 모든 수에 대해서 초과수 두 개의 합으로 나타낼 수 있는지를 찾으면 된다. 두 초과수의 합으로 N을 나타낼 수 있는지를 검사하기 위해서, 초과수 집합에 대해 두 번 루프를 돌면서 A + B == N을 만족하는지를 찾으면 너무 비효율적이므로, 다음과 같은 방식으로 검사 시간을 줄이도록 한다.

1. 28111 이하의 모든 초과수의 집합을 구한다.(23123-12). 이 집합을 A라 하자.
2. 24이상의 임의의 자연수 N에 대해서 N보다 작은 A의 원소 하나를 뺀다. 그리고 그 뺀 값이 A에 포함되어 있는지를 본다. 포함되어 있다면 N은 두 개의 초과수의 합임을 확인할 수 있다.
3. N보다 작은 초과수 중에서 2를 만족하는 값이 없다면 N은 두 개의 초과수의 합으로 나타낼 수 없는 값이다. (실제로는 N의 절반까지만 체크하면 된다.)
4. 3에서 구한 수들과 1~23 사이의 자연수를 모두 더하면 답이 된다.

이번 문제 역시 만 단위 숫자의 약수의 합을 구하는 것이기 때문에, 무식하게(?) 약수의 합을 구하는 함수를 사용하는 것으로 충분하다.

def facsum(n: int) -> int:
    l = int(n**0.5 + 0.5)
    s = 1 - (l if l * l == n else 0)
    for a in range(2, l + 1):
        if n % a == 0:
            s += a + n // a
    return s


def isovernum(n: int) -> bool:
    return facsum(n) > n


fs = [x for x in range(1, 28123) if isovernum(x)]
v = set(fs)


def test(n: int) -> int:
    if n < 24:
        return True
    for x in fs:
        if x > n // 2:
            break
        if (n - x) in v:
            return False
    return True


def main():
    print(sum(filter(test, range(1, 28123))))


if __name__ == "__main__":
    main()