프로젝트 오일러 51

오랜만에 다시 시작하는 프로젝트 오일러 문제이다. 참고로 50번을 넘어서면서부터는 꽤 어려운 문제들이 많이 나오고, 이런 저런 풀이들을 참고해봐도 영 이해가 안가는 문제도 몇 개 있다. (참고로 아직 100번까지는 몇 개 못 푼 문제들이 있어서 과연 몇 번까지 연재할 수 있을지도 모르겠다…) 일단 문제 갑니다…

두자리 숫자 *3 의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯개는 소수입니다. 56**3의 세 번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

56003, 56113, 56333, 56443, 56663, 56773, 56993

위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요. 치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우에는 거기에 0은 올 수 없습니다.

문제를 이해하기도 어려운 지경인데…. N 자리 숫자가 있고, 여기서 임의의 몇 개 숫자 위치를 정한 다음, 그 위치에 같은 숫자로 0, 1, 2 … 를 넣어서 만들어진 값이 소수가 되는 경우를 세어서 8개가 나오게 해야 한다. 그리고 그 중에서 가장 작은 소수를 구하는 것이다.

문제에서 8개가 나올 수 있는 숫자집단이 몇 개가 되는지는 언급하지 않고, 그저 “그 중에서 가장 작은 소수”를 찾으라고 했다. (8개 소수조합이 나올 수 있는 케이스가 1개 인지 그 이상인지는 알 수 없다.)

접근

이 문제의 가장 기본적인 접근은 12X45X 와 같은 식으로 치환되는 칸과 고정된 숫자를 조합하여, 템플릿을 만들고 치환되는 칸에 0부터 9까지를 넣고 이것이 소수가 되는지를 판별한다. 그리하여 8개의 소수가 만들어지면, 그 중에서 가장 작은 값을 출력해주면 끝난다.

문제는 2자리의 경우라면 1X 부터 9X 까지 81가지의 경우가 나오는데 치환하는 숫자의 개수가 고정되지 않았기 때문에 전체 자리수가 3자리, 4자리, 5자리로 올라갈 수록 체크해야 할 경우의 수가 급격히늘어난다는 점이 문제이다. 체크할 수 있는 개수를 줄이는 것이 필요한데, 의외로 문제의 조건인 “8개의 소수를 만든다”는 점에 착안해보자.

숫자를 치환해서 발생하는 값의 모든 자리수를 더했을 때, 그 값이 3의 배수가 되면 전체 수는 3의 배수가 된다. 그런데 0~9까지의 숫자를 바꿔가면 최소 4번의 3의 배수가 나타날 수 있다. (0, 3, 6, 9) 만약 치환되는 자리 외의 자리수의 합을 3으로 나눈 나머지가…

  • 0 이면 : 치환되는 숫자가 3의 배수일 때 Fail, 즉 최대 5개까지만 소수를 만들 수 있다.
  • 1 이면 : 치환되는 숫자의 합이 3n + 2 일 때 fail 한다. 역시 최소 3번은 실패한다.
  • 2 이면 : 치환되는 숫자의 합이 3n + 1 일 때 fail 한다. 최소 3번은 실패한다.

따라서 치환되는 숫자에 상관없이 전체 숫자의 합이 3의 배수가 되지 않도록 하는 방법은, 치환되는 숫자의 칸의 개수가 3의 배수개여야 한다.

그외에 마지막 자리 수가 짝수가 아닐 것, 그리고 첫 번째 자리 수는 0이 아닐 것의 조건이 추가될 수 있다.

참고로 원리만 파악하면 구현 자체는 큰 어려움이 없었던 다른 문제들과는 달리, 이 문제는 구현자체의 난이도도 제법 있다고 볼 수 있다.

치환영역 만들기

예를 들어 4자리 수 중에서 고정된 숫자가 ‘345’라고 가정해보자. 이 때 치환 영역의 위치는 X345, 3X45 등으로 다양하게 바뀔 수 있으며, 따라서 어느 위치의 숫자가 치환될 것인지에 따라서 다양한 값의 조합이 나올 수 있다. 이렇게 N 자리에서 m개의 고정 숫자를 제공한다면, 고정숫자와 변경숫자의 자리 조합을 만들어주고, 해당 조합에 따라서 필요한 숫자를 채워넣는 식으로 숫자를 구성하는 함수를 만들어야 한다.

치환 템플릿 생성 함수

먼저 숫자구성을 위한 템플릿을 생성하는 함수를 만들어보자. 0과 1을 사용하여 0은 변경숫자, 1은 고정숫자를 나타내도록하는 템플릿을 생성하는 함수를 만든다. 이건 간단하게 0과 1로 만들어진 문자열을 이용해서 순열을 생성하는 제너레이터를 만들면 되는 것이라, itertools 모듈 내의 permutations 함수를 사용하자.

from itertools import permutations

def make_templates(n):
  '''n자리 숫자에서 3개의 치환영역이 위치할 수 있는 모든 순열을 구한다.'''
  x = '0' * (n-3) + '111'
  return permutations(x)

숫자 생성함수

위에서 작성한 템플릿 생성함수는 N자리 숫자에서 3개의 교환숫자와 고정 숫자의 자리를 각각 0과 1로 표시할 수 있는 모든 조합을 생성하는 제너레이터 객체를 리턴한다. 이를 사용해서, 고정 숫자가 되는 n자리 정수와 (n+3)자리 템플릿을 이용해서 가능한 모든 숫자값을 생성하는 함수를 작성해보자.

루프의 매 반복마다 고정 숫자의 앞에서 하나씩 소모하거나 가변숫자를 쓰게 되므로, 별도의 인덱스를 사용하기 보다는 이터레이터를 얻어서 필요할 때마다 다음 글자를 얻는 식으로 처리했다.

def make_numbers(k, template):
  result = []
  for i in range(10):
    bucket = []
    x = iter(str(k))
    for j in template:
      # 템플릿의 현재 자리가 '0'이면 고정숫자, '1'이면 0~9의 숫자
      bucket.append(next(x) if j == '0' else str(i)) 
    if bucket[0] != '0':
      result.append(int(''.join(bucket)))
  return result

최종 정리

예상하기로는 답은 6자리 숫자에서 나올 것 같긴한데 혹시 몰라서 4, 5, 6자리에서 검사하도록 했다. 따라서 자리수 n을 받아서 해당 자리수에서 조건을 만족하는 값을 찾는 함수를 작성하고 이를 4, 5, 6 자리에서 각각 검사해보자.

참고로 소수검사는 100만 이하에서만 진행하면 되기 때문에 소수판별은 에라스토테네스의 체를 만들어서 검사하는편이 가장 빠를 것이다.

limit = 100_0000 # Python 3.6
seive = [False, False] + [True] * (limit - 1)
for i in range(2, int(limit**0.5)):
  if seive[i]:
    seive[i*2::i] = [False] * ((limit - i) // i)
    
is_prime = lamdba x: seive[x]

소수 판별 검사를 준비했으니, 이제 n 자리에 대해서 8개 조건을 만족하는 소수 그룹을 찾는 함수를 보자.

def p51(n=6):
  ## 6자리라면 가변숫자를 제외하면 3자리 숫자가 필요하므로, 
  ## 10**2 ~ 10**3 범위에서 찾는다.
  for k in range(10**(n-4), 10**(n-3)):
    for template in make_templates(n): # 일단 정해진 고정숫자에 대해서 템플릿별로 확인한다.
      groups = [x for x in make_numbers(k, template) if is_prime(x)]
      if len(groups) == 8:
        print(min(groups))
        return True
  return False

최종적으로는 4, 5, 6, 7 자리에 대해서 찾아본다. 작은 자리부터 확인하고, 실패하면 False를 성공하면 값을 출력하고 True를 리턴하도록 했으니, 성공한 후에 즉시 종료하도록 한다.

def main():
  for n in (4,5,6,7):
    if p51(n):
      return
    
%time main()

개선

대략 5초가까이 걸리는 시간을 좀 더 축약해보자.

  1. make_numbers에서 끝자리가 0,2,4,5,6,8로 끝나는 경우도 제외한다.
  2. 그랬을 때 결과의 수가 8개가 안된다면 어차피 소수검사를 할 필요가 없으니 빈 리스트를 리턴해버린다.
  3. 같은 이유로 템플릿의 끝자리가 가변숫자인 경우에도 []를 리턴해서 숫자를 생성할 필요가 없게 한다.
  4. 고정 숫자 k가 3의 배수라면, 생성되는 값 10개는 모두 3의 배수이므로, 이 부분도 건너뛰도록 한다.

이렇게 축약하면 대략, 1초대에 답을 구할 수 있다.