두자리 숫자 ▯3 의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯개는 소수입니다. 56▯▯3의 세 번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.
56003, 56113, 56333, 56443, 56663, 56773, 56993
위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요. 치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우에는 거기에 0은 올 수 없습니다.
http://euler.synap.co.kr/prob_detail.php?id=50
접근
문제의 이해부터 만만하지 않은 꽤 어려운 문제다. 문제에서는 N자리의 숫자 중 2개의 자리에 빈 칸을 만들고 이 빈칸에 0, 1, 2,…, 9를 넣은 10개의 수를 만들었을 때 이 중 8개가 소수가 되는 가장 작은 수를 구하라는 것이다. 예를 들어 1▯2▯7 이라는 템플릿이 있고, 여기 빈칸에 0~9의 숫자를 넣으면 10207, 11217, 12227, 13237,… 등의 숫자가 만들어지고, 이 중 8개가 소수인 경우를 찾는 것이다.
이 문제에서 난감한 점은 빈칸의 위치나 개수가 정해져있지 않다는 점이며, 몇 자리 수에서 시작해야 하는지 등 해결을 위해 고민하고 결정해야하는 단계가 너무 많다는 것이다. 우선, 언제나 그렇듯이 문제의 제약 조건을 먼저 찬찬히 살펴보도록 하자.
8개의 소수
우선 답은 아니겠지만, 2자리 수를 생각해보자. 2▯ 라는 템플릿을 사용하여 여기에 0~9를 넣으면 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 로 이중 23, 29 두 개만 소수이다. 사실 끝자리가 짝수 및 5인 숫자는 소수가 아니기 때문에, 1의 자리에는 빈 칸을 놓을 수 없다.
이번에는 1▯7을 보자. 107, 117, 127, 137, 147, 157, 167, 177, 187, 197 중에서 117, 147, 177 은 3의 배수로 소수가 될 수 없다. 만약 빈칸이 1개라면 빈칸에 올 수 있는 수는 3n, 3n+1, 3n+2 중 하나이므로, 다른 숫자들의 합과 상관없이 3~4회 정도는 3의 배수를 만들게 된다. 만약 빈칸이 2개라면? 6n, 6n+2, 6n+4 로 다른 숫자의 합과 무관하게 2회 이상 3의 배수를 만들게 된다. 빈 칸이 3개라면, 빈칸의 숫자의 합은 항상 9n, 9n+3, 9n+6이므로, 빈칸이 아닌 숫자의 합이 3의 배수가 아니라면 빈 칸의 숫자에 상관없이 3의 배수는 피할 수 있다.
그러면 이 조건으로 우리는 다음과 같은 제약조건들을 도출할 수 있다.
- 1의 자리 수에는 빈칸이 올 수 없다.
- 빈칸의 수는 3자리 이거나 최소한 3의 배수 개 만큼 필요하다. (따라서 전체 자리수는 최소 4자리이다.)
- 빈칸이 아닌 자리의 수의 합은 3의 배수여서는 안된다.
이 문제의 까다로운 점은 빈칸의 개수나 위치가 정해져 있지 않다는 것이고, 이 규칙에서 8개의 소수를 찾을 수 있는 가장 작은 소수를 찾으라는 것이다. 범위도 정해진 바가 없고 제약조건이 별로 없기 때문에 되게 막막한 느낌이 든다. 일단 사용할 수 있는 제약 조건을 최대한 준비해보자. 먼저 문제에서 언급한 “8개가 소수가 된다”는 부분부터 시작하자. (사실 여기가 핵심이다.)
치환 영역을 위한 템플릿
문제에서처럼 숫자와 빈칸으로 구성된 템플릿을 만들고, 빈칸에 0~9의 숫자를 넣어서 검사하는 단계를 위한 밑작업의 첫번째는 자리수에 따른 템플릿을 만드는 것이다. 템플릿은 *, _ 두 개의 문자로 조합된 문자열로, * 기호는 고정된 숫자를, _ 기호는 빈칸을 의미한다. 우리는 4자리 중에서 3개가 빈 칸, 5자리 중에서 3개가 빈 칸, 6자리 중에서 3개가 빈 칸… 등의 경우에 대해 템플릿을 모두 구해봐야 한다. 이 템플릿은 결국 두 가지의 중복된 기호를 사용하는 순열과 같다.
중복된 원소를 포함하는 것의 순열을 생성하는 제너레이터는 파이썬의 itertools 라이브러리에서 제공하지 않는다. 다만 이 블로그에서 이에 대한 내용은 한 번 다룬 바가 있으니, 이럴 때 유용하게 써먹을 수 있겠다. 같은 것을 포함하는 순열을 생성하는 함수를 바탕으로, 두 가지 문자로 템플릿을 만드는 함수를 작성할 수 있다.
from collections import Counter
def permutations_along_dups(ns, k=None):
def helper(head, es, k):
if k == 0:
yield head
for el, cnt in es.items():
# 만약 모두 소진한 요소라면 더 이상 추가하지 않는다.
if cnt == 0:
continue
yield from helper((*head, el), {**es, el:cnt - 1}, k-1)
yield from helper(tuple(), Counter(ns), len(ns) if k is None else k)
def create_template(a: int, b: int):
s = ['*'] * a + ['_'] * b
return [''.join(template) for template in permutations_along_dups(s) if template[-1] != '_']
# 테스트
# a = 고정 숫자의 개수, b = 빈 칸의 개수
create_template(2, 3)
# ['*___*', '_*__*', '__*_*', '___**']이제 정수 k를 입력받아, 각 자리 숫자와 3개의 빈칸으로 구성가능한 모든 템플릿과, 각 템플릿에 10개의 숫자를 넣은 리스트를 생성하는 제너레이터를 생성한다. 이 제너레이터에서 끝자리 수가 짝수나 5가 되는 숫자를 제외하고, 하나의 리스트에 사용 가능한 숫자가 8개 이하인 것을 다시 제외한다.
def generate_numbers(k: int):
ds = list(map(int, str(k)))
for template in create_template(k, 3):
res = []
for i in range(10):
temp = []
if template[0] == '_' and i == 0:
continue
for d in template:
temp.append(int(d) if d != '_' else i)
# print(temp)
res.append(reduce(lambda x, y: x * 10 + y, temp))
if len(res) < 8:
continue
yield res이제 1부터 k를 증가시켜가면서 generate_numbers()가 목록에서 소수가 8개 이상인지 판단하면 된다. 사실 전체 범위를 결정하는 것이 필요한데, 빈 칸의 자리수가 3개여야 하므로, 최대 6자리 내에서 등장할 것 같다. 7자리를 넘어가면 1개 고정 숫자 + 6개 빈칸이 발생한다. 아직 50번대이기 때문에 6자리내에서 답이 나올 거라 예상하고, 빈칸은 3자리 고정, 소수체는 1백만까지 준비하고, 찾을 때까지 돌려보도록 했다. 의외로 싱겁게 답이 금방 나온다. 1,000만까지 범위를 늘리더라도 시간은 크게 증가하지는 않는다.
%%time
def sieve(n):
s = [False] * 2 + [True] * (n - 1)
for i in range(int(n ** 0.5 + 1.5)):
if s[i]:
s[i+i::i] = [False] * ((n - i) // i)
return [i for i, x in enumerate(s) if x]
ts = set(sieve(1000_0000))
k, ds, i = 10, (1, 2), 0
done = False
while not done:
for xs in generate_numbers(k):
# print(k, xs)
if sum(1 if x in ts else 0 for x in xs) > 7:
print(min(xs), xs)
done = True
break
k, i = k + ds[i], i ^ 1
# 121313 [121313, 222323, 323333, 424343, 525353, 626363, 727373, 828383, 929393]
# CPU times: total: 203 ms
# Wall time: 197 ms