오랜만에 다시 시작하는 프로젝트 오일러 문제이다. 참고로 50번을 넘어서면서부터는 꽤 어려운 문제들이 많이 나오기 시작한다.
두자리 숫자 *3 의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯개는 소수입니다. 56**3의 세 번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.
56003, 56113, 56333, 56443, 56663, 56773, 56993
위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요. 치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우에는 거기에 0은 올 수 없습니다.
풀이는 커녕 문제를 이해하는 것도 쉽지 않은 지경이다. 문제의 예를 들어서 1_2_7 이라는 수가 있을 때 _ 자리에 0~9사이의 숫자를 넣는다. 이 때 빈칸의 숫자들은 항상 같다. 10207, 11217, 12227, 13237.. 이런식으로 말이다. 이렇게 숫자를 채워서 만든 수들 중에는 소수가 있을 수 있다.
이 문제의 까다로운 점은 빈칸의 개수나 위치가 정해져 있지 않다는 것이고, 이 규칙에서 8개의 소수를 찾을 수 있는 가장 작은 소수를 찾으라는 것이다. 범위도 정해진 바가 없고 제약조건이 별로 없기 때문에 되게 막막한 느낌이 든다. 일단 사용할 수 있는 제약 조건을 최대한 준비해보자. 먼저 문제에서 언급한 “8개가 소수가 된다”는 부분부터 시작하자. (사실 여기가 핵심이다.)
접근
먼저 2_ 의 경우를 보자 일의 자리에 0, 2, 4, 6, 8과 같은 짝수와 5가 오는 경우에는 소수가 될 수 없다. 항상 2의 배수이거나 5의 배수가 되기 때문이다. 따라서 빈칸이 일의 자리에 있는 경우 소수가 될 수 있는 가능성이 있는 숫자는 1, 3, 7, 9 로 제한된다. 이 때 1, 7은 실제로 나눠지는 수가 있는지를 검사해서 알게 되지만, 다른 숫자들은 미리 차단할 수 있다.
이번에는 1_7 의 경우를 보자, 빈칸에 1, 4, 7 이 오면 3의 배수가 된다. 모든 숫자를 넣을 때 숫자의 합이 3의 배수가 되면 그 수는 소수가 될 수 없다. 빈칸의 숫자는 3n, 3n+1, 3n+2 중 하나가 되기 때문에 열 번 중 세 번이 3의 배수로 소수가 되지 않는다. 그럼 빈 칸이 두 개인 경우에도 6n, 6n+2, 6n+4 로 결국 3n, 3n+1, 3n+2 의 합이 나온다. 따라서 8개의 소수를 찾기 위해서는 빈칸의 개수가 3의 배수가 되어야 하고, 고정된 숫자의 합은 3의 배수가 아니어야 한다는 결론을 얻을 수 있다.
따라서
- 일의 자리는 고정된 숫자여야하고, 짝수이거나 5가 올 수 없다.
- 빈칸을 제외한 자리의 수의 합은 3의 배수여서는 안된디ㅏ.
치환영역 만들기
3자리의 빈칸을 가지고 변경되는 숫자 집합을 만들기 위해서는 각각의 자리가 고정 숫자인지 빈칸인지를 결정해야 한다. 고정된 숫자 몇 개와 빈칸을 조합할 때 사용할 템플릿을 만들고 템플릿을 사용해서 숫자를 생성해야 한다. 가장 먼저 해야할 것은 각 자리에서 빈칸과 고정칸의 가능한 분포를 만들어야 한다.
빈칸을 3개 포함하는 4자리 숫자를 생각하면 “#___” 와 같은 템플릿을 생각할 수 있다. 가능한 조합은 “#___”, “_#__”, “__#_”, “___#” 이 된다. 순열을 만드는 것은 itertools.permutations() 함수를 사용하면 되는데, 이 함수는 일반적인 순열을 생성한다. 여기서 “#” 문자와 “_” 문자는 서로 구별되지 않는 동일한 것이므로 중복 순열을 만드는 제너레이터를 작성해보자. 중복 순열을 생성하는 문제는 제법 까다로운데, yield from 문법을 써서 재귀 제너레이터를 만들면 매우 간단하게 처리할 수 있다.
from collections import Counter
def perms(xs):
def helper(prefix, ws):
# 준비된 모든 요소를 다 사용했다면 prefix 리턴
if all(v == 0 for v in ws.values()):
yield prefix
# 남아있는 각각의 요소 하나씩을 prefix에 붙이고, 그 요소를 제외한 남은
# 요소들을 전달하여 순열을 생성
for k in ws:
if ws[k] > 0:
yield from helper((*prefix, k), {**ws, k:ws[k]-1}
yield from helper((), Counter(xs))이를 활용해서 숫자 템플릿을 생성하는 함수를 만들 수 있을 것이다.
치환 템플릿 생성 함수와 숫자 생성 함수
중복 순열 생성기가 있으니 숫자를 위한 템플릿은 간단하게 만들 수 있다. 그리고 이 템플릿으로 실제 숫자를 배치해서 숫자를 생성하는 함수도 작성해보자.
def gen_templates(n: int, m: int=3):
"고정 숫자 n개와 빈칸 m개로 이루어진 템플릿을 생성한다"
s = "#" * n + "_" * m
return ("".join(t) for t in perms(s))
def make_numbers(k: int):
for template in gen_templates(len(str(k))):
if template.endswith('_'):
continue
s = list(str(k))
# s에서 템플릿에서 빈칸의 위치와 같은 위치에 _ 문자를 삽입
for i, code in enumerate(template):
if code == '_':
s[i:i] = '_'
s = ''.join(s)
# "1___3" 처럼 생성된 문자열에서 빈칸에 0~9 숫자를 넣어서 숫자 리스트 생성
res = [s.replace('_', str(i)) for i in range(10)]
res = [int(r) for r in res if s[0] != '0' and s[-1] not in '024568']
# 선행 조건을 만족하는 숫자가 8개 미만이면 폐기
if len(res) < 8:
continue
yield res
최종 정리
4자리부터 시작해서 7자리 사이에서 검사를 해보자. 대충 5,6 자리에서 답이 나올 수 있을 것 같긴 하다. make_numbers()에 3의 배수가 아닌 1자리~4자리 값을 주고 조건에 맞는 값을 찾으면 출력하고 중단한다. 소수 검사는 대략의 범위가 정해져있으니, 소수체를 만들어서 판별하도록 했다.
def main():
l = 10 ** 7
s = [1] * (l + 1)
s[:2] = [0, 0]
for i in range(2, int(l**.5+1.5)):
if s[i]: s[i*2::i] = [0] * ((l - i) // i)
for x in range(1, 10000):
if x % 3 == 0: continue
for xs in make_numbers(x):
if sum(1 for x in xs if s[x]) == 8:
print(min(xs), xs)
return파이썬 3.9에서 0.6초 대에 답이 나왔다. 이쯤 되면 나쁘지 않은 것 같다.