프로젝트 오일러 051

문제

51번 문제

일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수

사이냅소프트

제약조건

문제 자체에서 제약 조건에 대한 직접적인 언급이 없기 때문에, 제약 조건에 대한 많은 고민을 해야 하는 문제입니다.

한 가지 중요한 힌트는 빈 칸에 올 숫자를 0~9로 바꾸는 동안 소수가 8개 만들어져야 한다는 점입니다. 그렇다면 빈 칸에 올 숫자가 변경되더라도, 세 숫자의 합은 항상 3의 배수가 되어 수 전체의 숫자의 합이 3의 배수가 되지 않아야 한다는 조건이 필요합니다. 따라서 빈 칸의 수는 3개 혹은 6개가 되어야 합니다.

이 조건을 포함하여 다른 몇 가지 조건을 나열해보겠습니다.

1. 빈 칸을 포함하는 템플릿에서 1의 자리 (맨 끝자리) 숫자에는 1, 3, 7, 9 만 올 수 있습니다.
2. 맨 끝자리에는 빈 칸이 올 수 없으며, 첫번째 자리에도 빈 칸이 올 수 없습니다.
3. 빈 칸의 개수는 3 입니다. (혹은 3의 배수입니다.)
4. 빈 칸이 아닌 곳의 고정된 숫자의 합은 3의 배수가 될 수 없습니다.

이러한 조건을 만족하는 가장 작은 소수를 구하라고 했기 때문에, 5자리에서 7자리 사이에 답이 있을 거라고 추측할 수 있습니다. 만약 이 추측이 틀렸다면 8자리 이상에서 답을 찾아 보면 됩니다. 8자리 이상에서도 답이 나오지 않는다면 8자리에서 빈 칸이 6개인 경우도 찾아보고.. 점점 범위를 넓혀야겠지만, 우선은 여기까지 먼저 탐색해보겠습니다.

템플릿

5자리 수에서 3개의 빈 칸이 있는 경우를 생각해보겠습니다. 빈 칸을 *로, 빈 칸이 아닌 숫자는 편의상 2와 3이 있다고 가정합니다. 그러면 빈 칸의 위치가 결정돼있지 않기 때문에 ( *, *, *, 2, 3) 으로 만들 수 있는 순열로 숫자의 템플릿을 만들고, 다시 각각의 템플릿에 대해서 * 문자를 0~9로 치환한 정수를 만듭니다. 5자리에서 만들 수 있는 순열은 5 × 4 = 20가지 이고, 6자리에서는 6 × 5 × 4 = 120가지의 템플릿이 만들어집니다.

빈칸이 아닌 수를 2, 3(23)으로 하든 3, 2(32)로 하든 동일한 템플릿을 사용하게 되기에, 10~999까지의 모든 수 보다는 중복을 허용하는 조합을 사용하는 편이 조금이라도 불필요한 반복을 줄 일 수 있습니다.

from euler import seive, permutations_dup, combinations_with_dup

BLANK = "*"

s = seive(1000_0000)
m = set(s)


def gen(*n: str, ks: int = 3):
    if sum(map(int, n)) % 3 == 0:
        return
    bs = [BLANK] * ks
    ps = [*n, *bs]
    for xs in permutations_dup(ps):
        if xs[-1] not in "1379":
            continue
        if xs[0] == BLANK or xs[0] == "0":
            continue
        template = "".join(xs)
        ts = [int(template.replace(BLANK, str(i))) for i in range(10)]
        yield [t for t in ts if t in m]


def main():
    for L in range(2, 7):
        for ns in combinations_with_dup("0123456789", L):
            for i in gen(*ns):
                if len(i) > 7:
                    print(i)
                    return


if __name__ == '__main__':
    main()

아래는 지금까지 자주 사용한 함수 구현들을 모아놓은 euler 모듈이다.

from collections import Counter
from functools import wraps
from math import log10
from time import monotonic


def elapsed(f):
    @wraps(f)
    def inner(*args, **kwds):
        e = monotonic()
        r = f(*args, **kwds)
        print(f"{(monotonic() - e) * 1000:.3f}ms")
        return r

    return inner


def sieve(bound: int) -> list[int]:
    s = [True] * (bound // 2)
    for i in range(3, int(bound**0.5) + 1, 2):
        if s[i // 2]:
            s[i * i // 2 :: i] = [False] * ((bound - i * i - 1) // (2 * i) + 1)
    return [2] + [2 * i + 1 for i in range(1, bound // 2) if s[i]]


def sum_of_divs(n: int) -> int:
    l = int(n**0.5)
    s = 1 - (l if l * l == n else 0)
    a = 2
    while a <= l:
        if n % a == 0:
            n += a + n // a
        a += 1
    return s


def num_of_divs(n: int) -> int:
    l: int = int(n**0.5)
    s: int = 2 - (1 if l * l == n else 0)
    a: int = 2
    while a <= l:
        if n % a == 0:
            n += 2
        a += 1
    return s


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    if n < 9:
        return True
    k, l = 5, int(n**0.5 + 1.5)
    while k < l:
        if n % k == 0 or n % (k + 2) == 0:
            return False
        k += 6
    return True


def factors(n: int) -> list[tuple[int, int]]:
    res: list[tuple[int, int]] = []
    e = 0
    while n % 2 == 0:
        n, e = n // 2, e + 1
    if e > 0:
        res.append((2, e))
    p = 3
    while p < n**0.5:
        e = 0
        while n % p == 0:
            n, e = n // p, e + 1
        if e > 0:
            res.append((p, e))
    if n > 1:
        res.append((n, 1))
    return res


def span(n: int) -> list[int]:
    l = int(log10(n))
    res = []
    for i in range(l):
        res.extend(divmod(n, 10 ** (i + 1)))

    return res


def shift(n: int) -> list[int]:
    l = int(log10(n))
    res = []
    for i in range(l):
        q, r = divmod(n, 10 ** (i + 1))
        res.append(r * 10 ** (l - i) + q)
    return res


def permutations(xs, n=0):
    def helper(head, tail, k):
        if k == 0:
            yield head
            return
        for i, x in enumerate(tail):
            yield from helper((*head, x), (*tail[:i], *tail[i + 1 :]), k - 1)

    yield from helper((), xs, n if n > 0 else len(xs))


def combinations(xs, n=0):
    def helper(head, tail, k):
        if k == 0:
            yield head
            return
        for i, x in enumerate(tail):
            yield from helper((*head, x), tail[i + 1 :], k - 1)

    yield from helper((), xs, n if n > 0 else len(xs))


def combinations_dup(xs, n=0):
    def helper(head, tail, k):
        if k == 0:
            yield head
            return
        for i, x in enumerate(tail):
            yield from helper((*head, x), tail[i:], k - 1)

    yield from helper((), xs, n if n > 0 else len(xs))


def permutations_dup(xs, n=0):
    def helper(head, counter, k):
        if k == 0:
            yield head
            return
        for x in counter:
            p = counter[x]
            if p == 0:
                continue
            yield from helper((*head, x), {**counter, x: p - 1}, k - 1)

    yield from helper(tuple(), Counter(xs), n if n > 0 else len(xs))


if __name__ == "__main__":
    for xs in permutations_dup((2, 2, 3, 3, 3)):
        print(xs)