프로젝트 오일러 023

문제

23번 문제

두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?

사이냅소프트

특정 집합의 값의 합으로 나타낼 수 있는 수

정해진 임계값인 28,123보다 작은 수 중에서 초과수 두 개의 합으로 나타낼 수 없는 값들을 모두 찾아서 그 합을 구하는 문제입니다. 해석학적인 방법으로는 저 임계값을 더 낮출 수 없다고 했기 때문에, 전수 조사를 해야합니다. 따라서 28,123보다 작은 모든 초과수를 먼저 구하고, 다시 이 두 수의 합으로 나타낼 수 없는 값들을 찾으면 됩니다.

그러면 두 초과수의 합으로 나타낼 수 없는 값은 어떻게 찾을까요?

하나의 정수값 N에 대해서 이 수가 두 초과수의 합으로 표현할 수 있는지는, 초과수의 집합에서 초과수 a를 꺼내어, (N - a)가 초과수인지 보면 됩니다. (N - a) 역시 임계값보다 작은 초과수라면 위에서 만든 집합에 포함되어 있을테니, 다시 약수의 합을 계산해보지 않아도 됩니다.

하나의 정수 N에 대해서는 a는 N/2 이하의 값만 검사해보면 됩니다.

한 가지 방법으로는 체를 만드는 것입니다. 1∙∙∙28,123의 리스트를 만들어 놓고, 초과수의 집합에 대해 이중으로 루프를 돌면서 그 합에 해당하는 값을 0으로 만들면, 루프가 끝난 후에는 초과수의 합이 아닌 수들만 남아있게 되겠죠.

저는 첫 번째 방법을 택해서 풀도록 하겠습니다. 초과수 두 개의 합으로 나타낼 수 있는 가장 작은 수는 24이니, 1∙∙∙23 사이의 합은 미리 합산하고 24부터 체크를 시작하는 방식입니다. 또한 범위가 그리 크지 않아서 약수의 합 역시 루프를 돌면서 구하기로 했습니다.

def is_abundant_number(n: int) -> bool:
    if n < 12:
        return False
    s = 1
    l = int(n ** 0.5)
    k = 2
    while k < (l + 1):
        if n % k == 0:
            s += (k + (n // k))
        k += 1
    if l * l == n:
        s -= l
    return s > n


def main2():
    LIMIT = 28123
    A = list(x for x in range(1, LIMIT+1) if is_abundant_number(x))
    print(len(A))
    S = set(A)
    res = sum(range(24))
    for x in range(24, 28123):
        for y in A:
            if y > x / 2:
                res += x
                break
            if (x - y) in S:
                break
    print(res)