책 이야기

적어도 2개의 소수를 약수로 가지고 있는 수를 합성수라 한다. 예를 들어, 15=3x5, 9=3x3, 12=2x2x3이다.

(서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 30이하에 10개가 있다:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26

10⁸보다 작은 n에 대해, (서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 몇 개인가?

--------------------------------------------------------------------------

1억 이하의 숫자 중에 2개 이상의 소수의 곱으로 구성된 합성수가 몇 개인지 묻는 문제이다. 문제에서 (서로 다를 필요가 없는)으로 설명된 부분은 동일한 소수로 곱해도 된다는 뜻이므로, 예시와 같이 9=3x3을 허용하게 구현하면 된다.

빠른 계산을 위해서 1억 이하의 소수 목록을 구하고, 2중 반복문에서 소수끼리 서로 곱하게 해서 목록을 구하고, 파이썬의 집합을 이용해서 중복을 제거해서 구했다. 1억 이하의 소수가 5백만 개 이상 나오더니 목록을 구하면서 메모리 에러가 발생했다. 생각보다 리스트가 커져서 문제가 생긴 것 같았다.

그래서, 결과값 리스트를 만들지 않고, 생성되는 합성수의 갯수를 구하도록 바꿔서 답을 구할 수 있었다. 소수 2개의 곱을 구하는 것이어서 다른 약수가 있을 수 없기 때문에 중복을 제거하는 과정이 필요없었다.

1로만 구성된 숫자를 repunit이라 부른다. R(k)를 길이가 k인 repunit이라 정의하자. 예를 들어, R(6)=111111이다.

gcd(n,10)=1인 양의 정수 n에 대해 언제나 R(k)를 n으로 나눌 수 있는 k가 존재한다. 그러한 k 중 최소값을 A(k)라 하자. 예를 들어, A(7)=6이고, A(41)=5이다.

5보다 큰 모든 소수에 대해, p-1은 A(p)로 나눠진다. 예를 들어, p=41일 때, A(41)=5이며 40은 5로 나눠진다.

그러나, 합성수 중 이러한 특성을 가지는 것이 드물지만 있다. 처음 5개 숫자는 91, 259, 451, 481, 703이다.

gcd(n,10)=1이고 n-1을 A(n)으로 나눌 수 있는 처음 25개 숫자의 합계를 구하시오.

--------------------------------------------------------------------------

129번 문제를 해결했으면, 코드를 조금만 수정하면 해결 가능한 문제이다.

기존에는 검증 대상이 되는 숫자에서  2의 배수, 5의 배수를 제외했지만, 소수 목록을 만들어서 소수를 검증 대상에서 제외하는 과정을 추가하고, n-1을 A(n)으로 나눠지는 숫자를 찾으면 된다.

문제에서 요구한대로 코딩했는데도 처음에 오답이 나와 원인을 분석하는 데 시간이 조금 걸렸다. 원인을 찾아보니, 검증대상에서 제외할 소수목록을 1만 이하의 숫자를 대상으로 만들었는데 실제로는 1만 이상의 숫자까지 대상이 되면서, 제외되어야 하는 소수가 목록에 포함되었던 것이 문제였다.

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

    9 = 7 + 2×1²
    15 = 7 + 2×2²
    21 = 3 + 2×3²
    25 = 7 + 2×3²
    27 = 19 + 2×2²
    33 = 31 + 2×1²

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

크리스티안 골드바흐는 모든 홀수 합성수는 소수와 제곱수를 2배한 수를 합하여 구할 수 있다고 제안하였다.

    9 = 7 + 2×1²
    15 = 7 + 2×2²
    21 = 3 + 2×3²
    25 = 7 + 2×3²
    27 = 19 + 2×2²
    33 = 31 + 2×1²

이 추측은 틀린 것으로 드러났다.

소수와 제곱수를 2배한 수의 합이 되지 않는 가장 작은 홀수 합성수는 무엇인가?

--------------------------------------------------------------------------

합성수를 이해하는 것이 필요한데, 1보다 크며 소수가 아닌 자연수를 합성수라고 한다. 다르게 이야기하면 소수는 약수가 2개이므로, 약수가 3개 이상인 자연수를 말하는 것이다.

홀수이면서 소수가 아닌 수(합성수)를 대상으로, 그 수보다 작은 제곱수의 2배(2, 8, 18, 32, ...)를 차례대로 빼고 남은 수가 소수인지 판별하는 과정을 반복해서 수행하면 된다. 다음 합성수를 찾을 때 중간에 발견되는 소수는 소수 리스트에 추가하고, 해당 합성수보다 작은 제곱수의 2배도 리스트로 만드는 형태로 해서 조금 더 효율적으로 수행하도록 했다.