A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
진약수의 합계가 원래 숫자와 같은 숫자를 완전수라고 한다. 예를 들어, 28의 진약수의 합은 1+2+4+7+14=28이며, 이것은 28이 완전수임을 의미한다.
어떤 숫자 n의 진약수의 합이 n보다 작은 경우 부족, 진약수의 합이 n보다 큰 경우 과잉이라 한다.
1+2+3+4+6=16인 12는 가장 작은 과잉수 이므로, 24는 두 과잉수의 합으로 표현될 수 있는 가장 작은 수이다. 수학적 분석에 의해, 28213보다 큰 모든 자연수는 두 과잉수의 합으로 표현될 수 있다. 그러나, 두 과잉수의 합으로 표현될 수 없는 가장 큰 숫자는 이 상한보다 작다고 알려져 있지만, 분석에 따라 이 상한은 더 작아질 수 없다.
두 과잉수의 합으로 표현될 수 없는 모든 양의 정수의 합계를 구하시오.
--------------------------------------------------------------------------
자신을 제외한 약수의 합계가 자신과 같으면 완전수, 작으면 부족수, 크면 과잉수라고 하는 것을 이번 문제에서 처음 알았다. 28213보다 큰 모든 자연수는 두 과잉수의 합으로 표현 가능하므로, 두 과잉수의 합으로 표현할 수 없는 양의 정수는 28213 이하의 숫자 중에 있다. 즉, 1~28213 사이의 숫자 중에 두 과잉수의 합으로 표현할 수 없는 숫자를 구하면 되는 것이다.
특정 숫자가 두 과잉수의 합으로 표현 가능한지 확인하는 방법을 구현하는 것이 이 문제를 해결하는 데 가장 중요한 부분인데, 조금 단순한 방법으로 해결하기로 했다. 12~28213(실제는 12를 뺀 28201) 사이 숫자 중 과잉수를 구하고, 두 과잉수를 반복해서 더해서 나오는 숫자 중 28213보다 작은 수를 구한 후에, 집합을 활용해서 중복을 제거했다.