자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 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을 만족하는지를 찾으면 너무 비효율적이므로, 다음과 같은 방식으로 검사 시간을 줄이도록 한다.
- 28111 이하의 모든 초과수의 집합을 구한다.(23123-12). 이 집합을 A라 하자.
- 24이상의 임의의 자연수 N에 대해서 N보다 작은 A의 원소 하나를 뺀다. 그리고 그 뺀 값이 A에 포함되어 있는지를 본다. 포함되어 있다면 N은 두 개의 초과수의 합임을 확인할 수 있다.
- N보다 작은 초과수 중에서 2를 만족하는 값이 없다면 N은 두 개의 초과수의 합으로 나타낼 수 없는 값이다. (실제로는 N의 절반까지만 체크하면 된다.)
- 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()