오일러 프로젝트 60

오일러 프로젝트 60은 앞뒤로 이어붙여도 소수가 되는 특별한 관계를 갖는 소수끼리 모인 집합을 찾는 문제이다. 역시 시간이 관건이 되는 문제이다.

네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 1097, 7109 모두 소수입니다. 2, 7, 109, 673은 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다. 다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서 그 합의 최소값을 구하세요.

접근

여러 모로 까다로운 문제이다. 범위를 한정하기 어렵다는 것이 가장 큰 문제이다.  일단 2는 소수이지만 다른 소수 뒤에 붙여서 소수를 만들 수 없으므로 (2로 끝나는 짝수가 되므로) 제외하면 나머지 홀수인 소수들만 대상이 된다. 그리고 우리는 만들 수 있는 집합 중에서 원소의 합이 최소가 되는 경우를 우선 찾고자 한다. 따라서 가능한 작은 요소들로 위 조건을 만족하는 홀수의 부분집합을 다음과 같이 찾아보자.

1. 정렬된 홀수인 소수의 집합을 P라고 한다. (P = {3, 5, 7, 11, … })
2. 먼저 P에서 가장 작은 원소 3을 채택한다. 그리고 그 나머지 소수들에 대해서 차례로 “3A”, “A3” 이라고 각각 붙여 썼을 때 소수가 되는 A를 찾아나간다. 이렇게 3을 앞뒤로 붙여서 소수를 만들 수 있는 P의 부분집합을 이라고 하자.
3. 마찬가지로 7을 선택해서 (5는 역시 뒤에 붙으면 5의 배수가 되기 때문에 조건을 충족할 수 없다), 다시 P의 다른 원소들을 차례로 이어붙여 소수를 만드는 부분집합을 찾을 수 있다. 이는 이 된다.
4. 따라서 은 3과 7에 연결했을 때 두 경우 모두를 만족한다. 이는 의 원소 중에서 7에 대한 조건을 만족하는 부분집합이기도 하다.
5. 다시 의 원소중에서 가장 작은 원소부터 채택하여 나머지 원소들의 앞뒤에 붙였을 때 조건을 만족하는 것을 찾아나갈 수 있다. 그 값을 S라 한다면 이 과정으로 필터링된 결과는 가 될 것이다.
6. 이런 식으로 계속해서 필터링 되는 S, T, U.. 를 필터링해 나간다. 까지 구하게 된다면 이는 다섯개 소수를 골라잡았을 때 그 중 두 개를 서로 앞/뒤로 이어붙였을 때 항상 소수가 될 것이다.
7. 단, 이 때는 P_n 들이 모두 무한 집합이라는 가정이 필요하다. 우리는 실제로 무한 집합을 다룰 수 없으므로 임의 자리수까지의 소수를 찾아놓고 그 중에서 시작한다.
8. 만약 주어진 모집합에서 조건에 맞는 원소를 찾을 수 없다면, 최종적으로 추가한 n을 탈락 시키고 다음 번 소수로 재시도하는 백트래킹이 필요하다.

이 구현은 매우 복잡해 보이는데, 비슷한 동작을 계속 이어나가기 때문에 재귀로 구현했을 때 비교적 간단하게 풀 수 있을 것 같다. 일단 문제를 간단히 하기 위한 building block들을 준비해보자.

구현 (Swift)

먼저 숫자를 이어붙이는 작업에 대해서 생각해보자. Swift의 경우 문자열 > 더하기 > 다시 정수로 바꾸는 것보다는 로그를 이용해서 자리 수를 구하여 계산하는 쪽이 빠르게 처리된다.

func concat(_ a: Int, _ b: Int) -> Int {
  /// 두 정수를 주어진 순서대로 연결한 새 정수를 리턴한다.
  guard b > 0 else { return a }
  let c = Int(log10(Double(b))) + 1
  return a * Int(pow(10, Double(c))) + b
}
// 테스트함수
func test(_ a: Int, _ b: Int) -> Bool {
  /// concat으로 앞뒤로 연결한 두 정수가 모두 소수인지 검사한다.
  return isPrime(concat(a, b)) && isPrime(concat(b, a))
}

소수 검사 함수는 워낙 많이 썼으니, 그 구현은 생략하자.  이제 소수 부분 집합으로부터 조건에 맞는 집합을 찾아보자. 다음 함수 process는 사실상 이 문제를 푸는 모든 로직을 포괄한다.

1. 모든 대상이 되는 소수의 집합과 현재까지 몇 단계의 후보를 얻었는지를 인자로 받는다.
2. 전달받은 집합으로부터 각 멤버 p와 이어붙이기 테스트에 통과한 P_q 를 얻는다.
3. P_q로부터 LEVEL – 1 개가 모두 이어붙여지는 집합을 구하고, 여기게 p를 더하면 LEVEL개의 집합을 얻을 수 있다.
4. LEVEL이 0이되면 더 진행할 필요 없이, 대상 집합이 답이된다.
5. 만약 조건에 맞는 추가 원소 집합을 찾을 수 없으면 실패로 간주, 이전 레벨로 돌아가서 다음번 P_q의 멤버로 테스트한다.

구현은 다음과 같다.

func process(in xs: Set<Int>, level: Int) -> Set<Int>? {
  guard level > 0 else { return xs }
  for a in xs.sorted() {
    var ys = xs.filter{ $0 != a && test($0, a) }
    if ys.count < level - 1 {continue }
    if var result = process(in: ys, level: level - 1) {
      result.insert(a)
      return result
    }
  }
  return nil
}

3자리소수범위에서 찾아보고, 답이 없으면 자리수를 늘려가며 찾는다.

main: do {
  var l = 4
  while true {
    let limit = Int(pow(10, Double(l))
    let primes = Set(stride(from:3, through:limit, by:2))
    if let result = process(in: primes, level: 5) {
      print(result.reduce(0, +))
      break
    }
    l += 1
  }
}

Python 풀이

동일한 알고리듬으로 구성했다. 아무래도 Swift보다는 좀 느려서 소수 검사에 메모이제이션을 적용하면, 2초 가량 걸린다.

def memoize(f):
  m = dict()
  def i(n):
    if n in m: return m[n]
    r = f(n); m[n] = r
    return r
  return i
@memoize
def is_prime(n):
  if n < 2: return False
  if n in (2, 3): return True
  if n % 2 is 0 or n % 3 is 0: return False
  if n < 25: return True
  k, l = 5, n**0.5
  while k <= l:
    if n % k is 0 or n % (k+2) is 0: return False
    k += 6
  return True
def test(a, b):
  return is_prime(int(f"{a}{b}")) and is_prime(int(f"{b}{a}"))
def process(xs, level):
  if level == 0 : return set()
  for a in sorted(xs):
    ys = {x in x for xs if x != a and test(a, x)}
    if len(ys) < level - 1: continue
    result = process(ys, level - 1)
    if result is not None:
      result.add(a)
      return result
  return None
def e60():
  l = 4
  while True:
    limit = 10**4
    primes = {x for x in range(3,limit,2) if is_prime(x) }
    result = process(primes, 5)
    if result is not None:
      print(sum(result))
      return
    l +=1
%timeit e60()
# Wall time: 2.31s