오일러 프로젝트 46

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.

• 9 = 7 + 2×1²
• 15 = 7 + 2×2²
• 21 = 3 + 2×3²
• 25 = 7 + 2×3²
• 27 = 19 + 2×2²
• 33 = 31 + 2×1²

이 추측은 잘못되었음이 밝혀졌습니다. 위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=46

접근

문제에서 찾고자 하는 것은, (소수 + 2 x 완전제곱수)로 표현할 수 ‘없는’ 홀수 합성수 중 가장 작은 값을 찾는 것이다. 따라서 9부터 이 조건을 만족하는지를 검사하여, 만족하는 첫번째 값을 찾으면 된다. 그렇지만 하나의 수에 대해서 (소수 + 2 x 완전제곱수)로 표현할 수 없다는 것은 결국 전수검사를 해야 하므로 역시나 그 횟수를 줄이고 시간을 단축하는 방법을 찾는 것이 중요하다.

우선 임의의 양의 정수 n에 대해서 위 추측의 반례가 되는지를 검사하기 위해서는 다음의 로직을 사용한다.

1. n은 홀수다.
2. n은 소수가 아니다.
3. 3이상인, 즉 홀수인 소수와, 제곱수의 두 배를 더한 합이 n이다. 따라서, (n – 3) / 2 이하의 완전제곱수들을 s₁, s₂, s₃,… s_k 로 구한다.
4. 모든 n – (2 * s) 가 소수가 아니면, n은 소수 + 2 x 완전제곱수로 표현할 수 없는 수가 된다.

이 로직에서는 소수 검사를 많이 하게 된다. n보다 작은 소수체를 만들면 좀 빠르겠지만, 매 시행마다 소수체를 계속 재생성하는 것은 효율이 떨어진다. 그리고 검사 함수 밖에서 소수체를 만들기에는 범위가 명확하지 못하다. 따라서 반복 계산의 효율을 높이는 방법으로 ‘메모이제이션’을 선택한다.

메모이제이션

메모이제이션은 함수의 입력과 출력을 (키, 값) 쌍으로 묶어서 다른 곳-주로 lookup 에 비용이 적은 사전-에 저장해두는 것을 말한다. 그렇게해서 한 번 입력된 적 있는 파라미터에 대해서는 나중에 다시 계산하지 않고 즉시 저장된 결과를 리턴하는 것이다. 메모이제이션은 아래와 같은 간단한 데코레이터를 통해서 적용할 수 있다.

from functools import wraps

def memoize(f):
  cache = {}

  @wraps(f)
  def inner(*args):
    if args in cache:
      return cache[args]
    r = f(*args)
    cache[args] = r
    return r

  return inner

@memoize
def isprime(n):
  if n < 2:
    return False
  if n < 4:
    return True
  if n % 2 == 0 or n % 3 == 0:
    return False
  if n < 9:
    return True
  k, l = 5, int(n ** .5 + 1.5)
  while k < l:
    if n % k == 0 or n % (k + 2) == 0:
      return False
    k += 6
  return True

이제 소수 검사 함수가 준비되었으니, 골드바흐 추측의 반례인지를 검사하는 함수 test()를 아래와 같이 작성하고, 9부터 시작하여 각 홀수들을 검사하여 반례를 찾아보자.

%%time

def test(n):
  if n % 2 == 0 or isprime(n):
    return False
  l = int(((n - 3) / 2) **.5 + 1.5)
  k = 1
  while k < l:
    if isprime(n - 2 * k * k):
      return False
    k += 1
  return True

a = 9
while not test(a):
  a += 2
print(a)