프로젝트 오일러 046

문제

46번 문제

(소수 + 2×제곱수)로 나타내지 못하는 가장 작은 홀수인 합성수는?

사이냅소프트

골드바흐의 다른 추측

크리스티안 골드바흐는 원래 '골드바흐의 추측'이라는 문제로 유명합니다. 2보다 큰 모든 짝수는 2개 소수의 합으로 나타낼 수 있다는 것입니다. 이 문제에서 소개된 가설은 '골드바흐의 다른 추측'으로 불립니다.

어떤 홀수합성수를 m이라 하고, 이를 어떤 소수 p와 다른 자연수 n의 조합으로 나타낸다면, 수식으로 쓰면 다음과 같습니다.

m = p + 2 × (n · n)

p와 n이 모두 정해지지 않았기 때문에 1) m보다 작은 모든 소수 p에 대해서 이 식을 만족하는 자연수 n이 있는지 살펴보거나, 2) 가장 작은 소수 2를 대입하여 sqrt((m - 2) ÷ 2) 보다 작은 모든 n에 대해서 수식을 만족하는 p가 소수인지를 검사하는 방법이 있습니다.

이 두 가지 방법 중에서 저는 2) 의 방법을 선택할 것입니다. 100의 제곱근은 10 밖에 되지 않지만 100 미만의 소수는 25개나 있습니다. 조금 더 범위가 늘어나면 이 차이는 극적으로 벌어집니다. 1000의 제곱근은 31보다 조금 더 큰 수인데, 1000 보다 작은 소수는 168개나 있습니다. 따라서 m과 p, n의 관계식에서 n = 1, 2, ···, sqrt((m - 2) ÷ 2) 일 때, 각각의 p가 소수인지를 검사하여 조건을 만족하는 n, p가 하나라도 존재한다면 소수와 합성수의 제곱으로 표현할 수 있는 수로 보면 됩니다.

from functools import wraps
# M = p + 2×(n^2)
# n = sqrt((M - p) ÷ 2)

_cache: dict[int, bool] = {}
def isprime(n: int) -> bool:
    if n in _cache:
        return _cache[n]
    res = True
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    if n < 10:
        return True
    k, l = 5, int(n ** 0.5 + 1.5)
    while k < l:
        if n % k == 0 or n % (k + 2) == 0:
            res = False
            break
        k += 6
    _cache[n] = res
    return res




def test(m: int) -> bool:
    if isprime(m):
        return False
    l = int(((m - 2) / 2) ** 0.5 + 1.5)
    for i in range(1, l):
        p = m - (i * i) * 2
        if isprime(p):
            # print(f'{m} = {p} * 2×{i}^2')
            return False
    return True


def main():
    m = 9
    while True:
        if test(m):
            return m
        m += 2


if __name__ == '__main__':
    print(main())

작은 값이지만 같은 값에 대한 소수 체크를 계속 반복하기 때문에 캐싱을 통해서 반복을 피하면 시간을 크게 단축할 수 있습니다. 그리고 이 추측은 '홀수 합성수'를 대상으로 하기 때문에, m이 소수이지 않도록 체크하는 부분도 빼놓지 않아야 합니다.

참고로 이 문제의 답 역시 그리 크지 않은 수입니다. 그 보다 더 큰 값도 존재합니다만, 몇 개의 반례를 찾은 후에는 천만 이하의 홀수 합성수에 대해서는 오히려 이 추측에 대한 반례를 찾기 어렵습니다, m이 일정 크기 이상으로 커지면 이 추축에 끼워맞출 수 있는 p, n을 찾을 만큼 p가 충분히 많기 때문일 것으로 생각됩니다.