책 이야기

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

3330씩 커지는 등차수열 1487, 4817, 8147은 2가지 면에서 특이하다. (i) 세 숫자 모두 소수이고, (ii) 각 4자리 숫자는 서로의 순열이다.

1, 2, 3자리 소수에서는 이런 특성을 가지는 등차수열이 없으며, 4자리 숫자에서 하나의 등차수열이 더 있다.

이 수열의 3개 항목을 연결한 12자리 숫자는 무엇인가?

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

첫 시행착오는 3개의 숫자가 서로의 순열일 뿐이지, 한쪽 방향으로 각 자리수를 이동하는 것이 아니었는데 그런 방식으로 해결하려 했던 것이다. 방향을 잘못 잡았던 덕분에 문제를 처음부터 다시 해결해야 했다.

해결한 방법은 지금 생각하면 효율성은 낮지만, 4자리 소수를 구하고, 그 수로 만들 수 있는 순열 중 소수인 것을 구하고, 소수+순열이 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다.

이 방법의 성능을 개선할 방법으로는 4자리 소수 리스트를 만든 후에, 특정 숫자(소수)와 그 숫자로 만들 수 있는 순열 중 소수인 것을 소수 리스트에서 삭제하면서 구하고, 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다. 이렇게 하면 중복되는 소수여부 검사, 순열 작성 등의 부담이 줄어들 것이다.

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317 이다.

1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰ 의 마지막 10자리 숫자는 무엇인가.

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

글을 작성하는 시점 기준으로 30번 이후 처음으로 10만 명이 넘는 사람(정확하게는 115,578명)이 정답을 작성한 문제이다. 1000의 1000승을 구하는 것이 다른 언어였으면 최대값 제한으로 integer가 아닌 자료형을 사용하는 등 까다로웠겠지만, 파이썬에서는 그냥 계산해서 끝의 10자리 숫자를 구하면 되기 때문에 정답자가 많은 것 갈다.

The first two consecutive numbers to have two distinct prime factors are:

    14 = 2 × 7
    15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

    644 = 2² × 7 × 23
    645 = 3 × 5 × 43
    646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

2개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 2개의 숫자는 다음과 같다:

    14 = 2 × 7
    15 = 3 × 5

3개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 3개의 숫자는 다음과 같다:

    644 = 2² × 7 × 23
    645 = 3 × 5 × 43
    646 = 2 × 17 × 19.

4개의 서로 다른 소수를 인자로 가지는, 처음으로 연속되는 3개의 숫자를 구하시오. 이 중 첫 숫자는 무엇인가?

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

5번 문제를 풀 때 소인수분해를 구현할 만큼 파이썬을 이해한 것이 아니어서 우회하는 방법으로 해결했는데, 이 문제에서는 소인수분해를 이용해서 해결했다.

해당하는 숫자보다 작은 값을 가지는 소수 리스트를 만들어 나가면서, 해당 숫자를 소수 리스트의 값으로 차례대로 계속 나눠 몇 개의 소수로 구성되는지를 판별하는 것이다. 예를 들어, 45는 2로 나눠지지 않고, 3으로는 2번 나눠지고(45/3=15, 15/3=5), 5는 5로 1번 나눠지므로 소인수는 3,5인 2개로 판별한다.

문제에서 요구하는 대로 소인수분해를 단순하게 구현한 덕분에 답을 구하는 데 시간이 많이 소요되었다. 아무래도 이 문제에서 요구하는 것은 문제에 충실하게 답을 구하는 것 보다는, 좀 더 효율적으로 답을 구하는 방법을 생각해 보는 것일 수도 있겠다.

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

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

It can be verified that T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

삼각수, 오각수, 육각수는 다음 공식에 따라 생성된다:

T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755임을 알 수 있다.

삼각수이면서, 오각수, 육각수인 다음 숫자를 구하시오.

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

이 문제를 해결할 때에는 근의 공식을 생각하지 못해서, n번째 생성되는 삼각수와 같은 오각수, 육각수는 n보다 작다는 속성을 이용해서 풀었다(15를 보면, 삼각수에서는 n=5일때지만, 육각수는 n=3일 경우 15임).

즉, n번째 삼각수, 오각수, 육각수 리스트를 만들면 삼각수와 같은 값이 오각수, 육각수에 있는지 찾는 것을 반복하는 것이다.

앞문제에서 근의 공식을 적용했던 것을 생각해 보면, n 기준으로 오각수는 n=(1+(1+24Pn)**0.5)/6, 육각수는 n=(-1+(1+8Hn)**0.5)/4가 되므로 삼각수를 구하고, 해당 값을 오각수, 육각수 공식에 대입해 결과가 자연수가 나오는지 확인하는 것이 좀 더 빠른 해결방법이 될 것 같다. 그리고, 285번째 삼각수인 4075가 제시되어 있으니, 그 이후로 값을 찾으면 실행시간을 좀 더 줄일 수 있을 것이다.