오일러 프로젝트 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 이하의 모든 수에 대해서 두 초과수의 합으로 나타낼 수 있는지를 검사한다.
- 28123이하의 모든 초과수를 구한다.
- 12…28123사이의 모든 수에 a에 대해서 초과수 2개의 합으로 나타낼 수 있는지 검사한다.
- 이는 a보다 작은 초과수, 즉 a보다 작은 1.의 부분집합의 원소 b에 대해서 (a – b)가 초과수인지 검사하면 된다. (b + (a – b) = a 이므로).
- 3의 조건을 만족하지 않는 모든 정수의 합과 1~11의 합을 더하여 답을 구한다.
모든 약수의 합을 구하여 초과수인지를 판별하기 위해서는 해당 자연수의 제곱근 이하의 모든 자연수로 나눠 그 제수와 몫을 합하면 된다. 한계값 자체가 만단위 수 이기 때문에 소인수분해를 이용하는 것보다 이렇게 단순 루프를 이용하는 것이 좀 더 빠르게 처리된다. 또한 임의의 자연수 n에 대해서 이 n이 두 초과수의 합으로 이루어지는지를 검사할 때, 초과수 집합에서 임의의 두 원소 a, b를 추출해 더해서 검사하는 것보다 하나만 추출하여 그 차이가 다시 초과수가 되는지를 보는것이 빠를 것이다. (루프를 이중으로 돌 것을 한 번만 돌면 되게 한다.)
풀이는 다음과 같다.
def sum_of_divisors(n):
s, a, l = n + 1, 2, n**0.5
while a < l:
if n % a is 0:
s += a + n // a
a += 1
if a*a == n:
s += a
return s
def e023():
targets = {x for x in range(12, 28124) if sum_of_divisors(x) > x * 2}
def test(n):
for i in targets:
if i >= n:
break
if (n-i) in targets:
return True
return False
result = list(range(1, 12))
for i in range(12, 28124):
if not test(i):
result.append(i)
print(sum(result))
%time e023()
# Wall time: 1.26 s보너스 : Swift 풀이
동일한 알고리듬의 Swift 풀이이다. 수행시간은 약 1.8초 가량된다.
import Foundation
func sumOfDivisors(of n: Int) -> Int {
var s = n + 1
var a = 2
let l = Int(sqrt(Double(n)) + 0.5)
while a < l {
if n % a == 0 { s += a + (n / a) }
a += 1
}
if a*a == n { s += a }
return s
}
let targets = Set<Int>((12...28123).filter{ sumOfDivisors(of: $0) > $0 * 2 })
let test: (Int) -> Bool { x in
for i in targets where i < x {
if targets.contains(x-i) { return true }
}
return false
}
var result: [Int] = Array(1...11)
for i in 2...28123 {
if !test(i) { result.append(i) }
}
print(result.reduce(0, +))