오일러 프로젝트 23

오일러 프로젝트 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 이하의 모든 수에 대해서 두 초과수의 합으로 나타낼 수 있는지를 검사한다.

  1. 28123이하의 모든 초과수를 구한다.
  2. 12…28123사이의 모든 수에 a에 대해서 초과수 2개의 합으로 나타낼 수 있는지 검사한다.
  3. 이는 a보다 작은 초과수, 즉 a보다 작은 1.의 부분집합의 원소 b에 대해서 (a – b)가 초과수인지 검사하면 된다. (b + (a – b) = a 이므로).
  4. 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, +))