책 이야기

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배도 리스트로 만드는 형태로 해서 조금 더 효율적으로 수행하도록 했다.

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

1406357289는 0에서 9까지 숫자로 구성되어 있으므로 0에서 9 pandigital 숫자이지만, 다소 재밌는 부분 문자열 속성을 가지고 있다.

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

d₁을 첫번째 문자, d₂를 2번째 문자 등으로 부르면 다음을 알 수 있다:

• d₂d₃d₄=406은 2로 나눌 수 있음
• d₃d₄d₅=063은 3으로 나눌 수 있음
• d₄d₅d₆=635은 5로 나눌 수 있음
• d₅d₆d₇=357은 7로 나눌 수 있음
• d₆d₇d₈=572은 11로 나눌 수 있음
• d₇d₈d₉=728은 13으로 나눌 수 있음
• d₈d₉d₁₀=289은 17로 나눌 수 있음

이런 속성을 가진 0에서 9 pandigital 숫자의 합계는 얼마인가?

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

32번 문제로 처음 나와 이번에 4번째 나오는 pandigital 관련 문제의 난이도가 계속 올라간다.

반목문을 이용해 10자리 pandigital 숫자를 차례대로 만들고, 숫자를 3개씩 6개로 쪼개어서 각 숫자가 2, 3, 5, 7, 11, 13, 17로 나눠지는지 확인하여 해당하는 숫자의 합계를 구하면 된다.

숫자를 문자열/리스트로 바꾸는 것, 이것을 활용해 숫자의 일부를 잘라내는 것 등이 익숙해져 파이썬으로 답을 구하는 데 그리 어렵지 않았다. 성능 향상을 위해 4번째 숫자가 짝수인지만 확인해도 2로 나눠지는지 검증 가능하고, 6번째 자리고 0,5인지 확인해도 5로 나눠지는지 검증 가능하지만 큰 차이는 없을 것 갈아 다른 숫자와 동일한 형태로 3자리 숫자를 잘라내어 검증하는 형태로 구성했었다.

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

1부터 n까지 한번씩 모든 숫자를 사용하여 만들어진 n자리 숫자를 pandigital이라 부른다. 예를 들어, 2143은 4자리 pandigital이며 또한 소수이다.

가장 큰 n자리 pandigital 소수는 무엇인가?

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

답을 구하는 기본 원리는 간단하다. 각 자리 숫자에 대한 pandigital을 구하고 소수인지 확인하여 가장 큰 값을 찾으면 되는 것이다. 실제 그렇게 구현했고, 시간도 많이 걸리지 않아 다음 문제로 넘어갔던 것 같은데, 이 글을 쓰면서 생각해보니 효율을 높일 방법이 여러가지가 있어 보인다.

우선, 작은 숫자부터 올라가면 모든 조합을 확인해야 가장 큰 pandigital 소수를 찾을 수 있지만, 큰 숫자부터 내려오면서 pandigital을 검증하면 가장 먼저 찾는 소수가 가장 큰 pandigital 소수가 된다. 그리고, 1~9의 합이 3의 배수이기 때문에 9자리는 모든 숫자가 3으로 나눠지므로 소수가 아니고, 1~8의 합도 마찬가지로 3의 배수이기 때문에 8자리 숫자도 검증할 필요가 없다. 즉, 7자리 숫자의 가장 큰 pandigital에서 시작하여 내려오면서 가장 먼저 나오는 소수가 해답이 되므로, 훨씬 빠른 시간에 답을 구할 수 있을 것이다.

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

3797은 재미있는 속성을 가지고 있다. 자신이 소수이면서, 왼쪽에서 오른쪽으로 자릿수를 하나씩 제거할 때 각 단계에서 남는 숫자인 3797, 797, 97, 7 모두 소수이다. 비슷하게 오른쪽에서 왼쪽으로 제거하는 작업을 하면 남는 3797, 379, 37, 3도 소수이다.

왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 제거해 나갈 수 있는 11개 밖에 없는 소수의 합계를 구하시오.

주의: 2, 3, 5, 7은 절단 가능 소수(truncatable primes)로 고려하지 않는다.

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

검색해 보니 절단 가능 소수라는 말로 번역되고 있는 truncatable prime에 대한 문제이다. 소수가 여러 한계와 다양한 특성이 많아서인지 프로젝트 오일러에는 소수를 활용하는 문제가 많이 나온다.

왼쪽으로 지워나가는 것은 해당 숫자의 자릿수에 해당하는 숫자로 나눴을 때 나머지를 구하는 방법을 쓰고(3797을 1000으로 나눠 나머지인 797을 활용), 오른쪽으로 지워나가는 것은 해당 숫자를 10으로 나눠 몫을 구하는 방법을 반복해서 구했다.

그리고, 2, 3, 5, 7은 해당하지 않는다고 했으므로 11부터 시작해서 (소수가 아닌 짝수를 제외하고) 2씩 증가해가며 소수인지 확인하고, 소수인 경우에는 왼쪽, 오른쪽으로 지워나가며 소수 여부를 확인하게 구현했다. 이렇게 하면서 11개가 나오면 중단하면 된다.

2부터 시작하는 소수 리스트를 만들면서 왼쪽, 오른쪽으로 지우면서 나오는 소수를 매번 직접 판별하는 것이 아니라 소수 리스트에 있는지 확인하는 형태로 하면 속도가 조금 빨라질 수 있다.

문제를 해결하고 나서 다른 분이 해결했던 방법을 참조해 보니 속도를 더 개선할 수 있는 방법으로, 왼쪽에서 지워나갈 때 1의 자리 숫자가 소수가 아니면 결국 '절단 가능 소수'가 아닌 것으로 판별하게 되므로 이미 제거했던 짝수(0, 2, 4, 6, 8) 이외에 (1, 5, 9)가 있는 경우도 계산하지 않아도 된다. 즉, 소수 중에서 1의 자리 수가 3, 7인 경우에만 절단 가능 소수가 될 수 있으므로 이들 대상으로만 판별하면 되는 것이다.

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

숫자 197의 자릿수를 바꿔 만들어지는 197, 971, 719 모두가 소수이기 때문에 순환소수(circular prime)이라 불린다.

100 이하의 수에는 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97의 13개 순환소수가 있다.

백만 이하의 수에는 몇 개의 순환소수가 있는가?

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

순환소수라 불렀지만 수학 용어는 아니고 임의로 붙인 명칭이다. 숫자를 한 방향으로 회전시키면서 나온 숫자가 소수인지 판별하면 된다.

단순하게 생각해보면 2부터 백만까지 반복해가면서 소수인지 판별하고, 자릿수를 바꿔 만들어지는 수가 모두 소수인지 판별하는 방법이 있다. 하지만, 소수인지 판별하는 것이 상대적으로 시간이 많이 소요되는 과정이기 때문에 성능이 나쁠 것 같아 다른 접근을 하기로 했다.

미리 2부터 백만까지의 소수를 리스트로 만들어 놓고, 리스트에 있는 소수를 대상으로 자릿수를 바꿔 만들어지는 수가 만들어 놓은 소수 리스트에 있는지 확인하는 방식으로 소수 여부를 판별하게 했다. 그리고, 조금 더 계산 속도를 빠르게 만드는 방법으로는 소수인 숫자 어딘가에 짝수나 5의 배수가 있으면 순환하는 중 1의 자리에 오게 되면 소수가 아니게 되기 때문에(2의 배수 or 5의 배수), 각 자릿수 중에 0,2,4,6,8과 5가 있으면 소수가 아닌 것으로 보고 다음 숫자로 넘어가게 할 수 있다.

Euler discovered the remarkable quadratic formula:

n²+n+41

It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40,40²+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,41²+41+41 is clearly divisible by 41.

The incredible formula n²−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

    n²+an+b, where |a|<1000 and |b|≤1000
    where |n| is the modulus/absolute value of n
    e.g. |11|=11 and |−4|=4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

오일러는 놀라운 이차방정식을 발견했다:

n²+n+41

이 공식은 0≤n≤39 범위에서 연속된 40개의 소수를 만들어내는 것으로 밝혀졌다. 그러나, n=40일 때, 40²+40+41=40(40+1)+41은 41로 나눠지고, 당연하게도 n=41일 때,41²+41+41은 분명하게 41로 나눠진다.

믿을수 없는 공식 n²−79n+1601은 0≤n≤79에서 80개의 연속된 소수를 만드는 것으로 밝혀졌다. 계수인 -79와 1601의 곱은 −126479이다.

|a|<1000이고, |b|≤1000인 다음 형태의 이차방정식 n²+an+b을 생각해 보자.
|n|은 n의 계수값/절대값이다. 즉, |11|=11이고, |−4|=4이다.

n=0으로 시작해 최대 길이의 연속된 소수를 만들어 내는 계수 a와 b의 곱을 구하라.

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

아직 26번을 해결하는 아이디어가 떠오르지 않아 생략하고 진행한다.

문제는 읽기 까다로운 편인데, 반복문을 이용한 단순한 접근으로 해결 가능하다. a는 -999에서 999, b는 -1000에서 1000까지 검증하는 반복문에, n을 0부터 대입하면서 가장 길게 소수를 만드는 경우를 계산하면 된다.

출제 의도는 좀 더 효율적으로 계산하는 방법을 고민하기를 원했던 것 같은데 단순한 방법으로 해결 가능했다.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

10 이하 소수의 합은 2+3+5+7=17이다.

2백만 이하 소수의 합을 구하시오.

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

단순하게 200만 이하의 소수를 구해서 합했는데, 속도를 빠르게 하기 위해서 2, 3으로 나눠지는 숫자는 소수 여부를 판별하지 않고 지나가도록 했다.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

처음 6개 소수는 2, 3, 5, 7, 11, 13이고, 6번째 소수는 13이다.

10001번째 소수는 무엇인가?

소수를 판별하는 함수를 사용하고, 10001번째 소수를 구하면 된다.

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

소수를 판별하는 함수는 프로그램의 성능에 영향을 많이 주기 때문에 빨리 결과를 볼 수 있도록 속도가 빠른 것이 좋고, 10001번째 소수는 리스트의 길이로 판별하는 것보다는 카운트를 사용하는 것이 더 효과적이지만, 값을 정확히 계산하는지 확인하기 위해 리스트 형태로 처리하였다.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195의 소인수는 5, 7, 13, 29이다.

600851475143의 가장 큰 소인수는 무엇인가?

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

이렇게 큰 수가 나오기 때문에 프로그램을 작성하지 않으면 답을 구하기가 어려운 것이 프로젝트 오일러의 문제이다. 일단 소인수는 소수이면서 인수인 숫자이다. 12를 예로 들면 12를 나눌 수 있는 1, 2, 3, 4, 6, 12가 인수가 되며, 이 중 소수인 2, 3이 소인수가 된다.

간단히 생각해 보면 2가지 접근이 가능하다. 2부터 1씩 키워가면서 나눠지는 숫자(나머지가 0)이면서 소수인 숫자 중 가장 큰 수를 찾는 방법이 있고, 소수를 구해놓고 600851475143을 나눌 수 있는 가장 큰 숫자를 구하는 방법도 있다.

인수를 구하고 소수인지 판별하는 전자의 방법으로 해결했으며, 함수를 이용하여 소수 여부를 확인하였다.