프로젝트 오일러 046

골드바흐의 다른 추측

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

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

m = p + 2 × (n · n)

이 식을 통해서 추측의 반례를 찾기 위해서는 m보다 작은 모든 소수 p에 대해, 식을 만족하는 n이 존재하는지 찾거나, 반대로 m의 절반의 제곱근 이하의 n에 대해서 수식을 만족하는 소수 p가 있는지를 찾아보는 방식으로 탐색해야 합니다.

여기서는 후자가 더 유리한 방법일 것으로 생각됩니다. 소수의 분포는 어떤 규칙을 따르지 않지만, 어떤 수보다 작은 소수의 개수는 그 수의 제곱근보다는 많기 때문입니다. 100의 제곱근은 10 밖에 되지 않지만 100 미만의 소수는 25개나 있습니다. 조금 더 범위가 늘어나면 이 차이는 극적으로 벌어집니다. 1000의 제곱근은 31보다 조금 더 큰 수인데, 1000 보다 작은 소수는 168개나 있습니다.

따라서 m의 절반의 제곱근보다 작은 자연수 n에 대해서 m - 2 × (n · n) 이 소수인지를 검사하고, 소수를 만드는 n이 없다면 이 때 m이 가설의 반례라고 할 수 있습니다.

from euler import timeit, isprime

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):
            return False
    return True


@timeit
def main():
    m = 9
    while True:
        if test(m):
            print(m)
            break
        m += 2


if __name__ == '__main__':
    main()

의외로 값은 그리 크지 않은 수이기 때문에 소수 검사 함수를 메모아이즈하지 않아도 답을 빠르게 찾을 수 있습니다.