[Project Euler] 51. Prime digit replacements

1. 개요

    문제는 이곳에서 확인할 수 있다. 숫자 56**3의 3번째, 4번째에 같은 숫자 10개를 넣으면 그 중 7개가 소수가 된다. 즉,  56003, 56113, 56333, 56443, 56663, 56773 그리고 56993이 그 소수들이다. 이와 같이, 자리의 일부를 같은 숫자로 치환하여 8개의 소수를 만들수 있는 가장 작은 수를 구하는 것이 문제의 목표이다. 단, 치환하는 자리는 인접하지 않아도 된다.

2. 구현

    문제를 제대로 파악하지 못해 굉장히 시간이 오래 걸렸다. 처음에는 예시와 같이 치환해야 하는 자리가 2개로 제한되어 있다고 생각하였고 그렇게 구현하였다. 하지만 도저히 답이 나오지 않자 다른 사람들의 의견을 참고하였고 치환해야 하는 개수의 제한이 없다는 것을 알게 되어 바로 다시 구현하였다.

    중복되는 숫자가 2개 이상 존재하는 소수에 대하여 중복되는 위치의 조합을 파악하고 그 조합에 숫자를 대입해가면서 답을 찾아간다. 예를 들어 119993에는 1과 9가 중복된다. 1을 치환할 수 있는 자리는 1, 2번째 자리이므로 여기에 1부터 9까지의 숫자를 대입한다. 또한 9를 치환할 수 있는 자리는 3, 4, 5번째, 3, 4번째 그리고 4, 5번째 자리이므로 여기에 0부터 9까지의 숫자를 대입한다. 소수를 찾는 작업에는 sympy를, 위치의 조합을 찾는 작업에는 itertools를 사용한다. 코드는 다음과 같다. 

# -*- coding: utf-8 -*-

import sympy as s
import itertools as it
import time as t

start_time = t.time()

n = 1
end = False

while not end:

    # 1. 소수를 찾고 각 자리로 분해.
    prime = s.prime(n)
    prime_digit = list(map(int, str(prime)))

    # 2. 같은 숫자가 2개 이상 있는지 학인하고 진행.
    unique_digit = list(set(prime_digit[:-1]))

    if len(prime_digit)-1 == len(unique_digit):
        n += 1
        continue

    # 3. 같은 숫자가 무엇이고 어디에 있는지 확인.
    same_digit = prime_digit[:-1]

    for d in unique_digit:
        same_digit.remove(d)

    same_digit = list(set(same_digit))
    same_digit_pos = {}

    for d in same_digit:
        same_digit_pos[d] = [i for i, v in enumerate(prime_digit[:-1]) if v == d]

    # 4. 바꿀 수 있는 모든 위치를 파악.
    for k, v in same_digit_pos.items():
        same_digit_pos[k] = list()
        for l in range(len(v), 1, -1):
            same_digit_pos[k] += list(it.combinations(v, l))

    same_digit_pos = [pos for pos_list in same_digit_pos.values() for pos in pos_list]

    print(prime, same_digit_pos)

    # 5. 해당 위치에 숫자를 넣어보면서 소수인지 파악
    for pos in same_digit_pos:
        tmp_prime_digit = prime_digit[:]
        tmp_prime_list = list()

        for d in range(1 if 0 in pos else 0, 10):
            for p in pos:
                tmp_prime_digit[p] = d

            prime_candidate = int(''.join([str(d) for d in tmp_prime_digit]))

            if s.isprime(prime_candidate):
                tmp_prime_list.append(prime_candidate)

        if len(tmp_prime_list) == 8:
            print(prime, sorted(tmp_prime_list))
            end = True

    n += 1

end_time = t.time()
print(end_time - start_time)

    답은 121313이다.

3. 생각해 볼 점

    문제를 푼 후 다른 사람들은 어떻게 해결하였는지 살펴보았는데, 역시 놀라운 직관이 많았다. 먼저, 답의 조건은 8개의 소수 중 가장 작은 값이므로 치환되는 숫자는 적어도 3보다 작아야 한다. 그리고 치환되는 숫자의 개수는 3의 배수여야 한다. 왜 그러한지 보자.

    중복되는 숫자의 개수가 2개라고 하자. 치환하는 숫자들 중 4개는 3으로 나누어 떨어지고 6개는 그렇지 않다. 즉, 0, 3, 6, 9로 치환하면 그 숫자들의 합은 3의 배수가 되고 3개는 나머지 1을 갖고 3개는 나머지 2를 갖는다. 이제 치환되지 않은 남은 숫자들의 합은 3의 배수이거나 그렇지 않을 것이다. 만약 3의 배수라면 치환된 수 4개가 3의 배수가 되어 답이 될 수 없다. 치환되지 않은 남은 숫자들의 합이 3의 배수가 아니어도 모든 숫자들의 합 중 적어도 3개는 3의 배수가 된다. 중복되는 숫자가 3의 배수가 아닐 때에는 모두 이러한 현상이 발생한다. 따라서 우리가 찾는 소수는 0, 1 또는 2가 3의 배수번 반복되는 수일 것이다. 이를 반영하여 코드를 다시 작성한다. 

# -*- coding: utf-8 -*-

import sympy as s
import itertools as it
import time as t

start_time = t.time()

n = 1
end = False

while not end:

    # 1. 소수를 찾고 각 자리로 분해.
    prime = s.prime(n)
    prime_digit = list(map(int, str(prime)))

    # 2. 같은 숫자가 2개 이상 있는지 학인하고 진행.
    unique_digit = list(set(prime_digit[:-1]))

    if len(prime_digit)-1 == len(unique_digit):
        n += 1
        continue

    # 3. 같은 숫자가 무엇이고 어디에 있는지 확인.
    same_digit = prime_digit[:-1]

    for d in unique_digit:
        same_digit.remove(d)

    same_digit = list(set(same_digit))

    # 3.1. 추가, 같은 숫자가 0, 1, 2가 아니라면 최소가 아님.
    if not any(d in [0, 1, 2] for d in same_digit):
        n += 1
        continue

    same_digit_pos = {}

    for d in same_digit:
        same_digit_pos[d] = [i for i, v in enumerate(prime_digit[:-1]) if v == d]

    # 4. 바꿀 수 있는 모든 위치를 파악.
    for k, v in same_digit_pos.items():
        same_digit_pos[k] = list()
        for l in range(len(v), 1, -1):
            same_digit_pos[k] += list(it.combinations(v, l))

    same_digit_pos = [pos for pos_list in same_digit_pos.values() for pos in pos_list]

    # 5. 해당 위치에 숫자를 넣어보면서 소수인지 파악
    for pos in same_digit_pos:

        # 5.1. 추가, 반복되는 수의 개수가 3의 배수여야만 답이 될 가능성이 있음.
        if len(pos) % 3 != 0:
            continue

        tmp_prime_digit = prime_digit[:]
        tmp_prime_list = list()

        for d in range(1 if 0 in pos else 0, 10):
            for p in pos:
                tmp_prime_digit[p] = d

            prime_candidate = int(''.join([str(d) for d in tmp_prime_digit]))

            if s.isprime(prime_candidate):
                tmp_prime_list.append(prime_candidate)

        if len(tmp_prime_list) == 8:
            print(prime, sorted(tmp_prime_list))
            end = True

    n += 1

end_time = t.time()
print(end_time - start_time)

최초로 구현한 코드보다 약 8배 가량 더 빨리 동작한다.