책 이야기

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가 제시되어 있으니, 그 이후로 값을 찾으면 실행시간을 좀 더 줄일 수 있을 것이다.

Pentagonal numbers are generated by the formula, P_n=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference are pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

오각수는 P_n=n(3n−1)/2 공식에 따라 생성된다. 처음 10개 오각수는 다음과 같다:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

P₄ + P₇ = 22 + 70 = 92 = P₈임을 알 수 있다. 그러나, 둘의 차이인 70 − 22 = 48은 오각수가 아니다.

두 수의 합과 차이가 모두 오각수이고 D = |P_k − P_j| 가 최소화되는 두 오각수 P_j and P_k를 찾으시오. D의 값은 얼마인가?

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

이 문제는 신기하게도 어렵지 않게 해결했는지 방법은 기억이 나지 않으면서, 어떻게 접근해야 할 지 난감한 것을 보니 상상하지 못할 단순하고 비효율적인 방법으로 해결했던 것 같다.

가능한 접근으로는, 오각수 리스트를 만들면서 새로운 오각수를 추가하면 기존 리스트의 숫자와 차이를 비교해 오각수가 되는 경우를 찾고 해당 경우에 합이 오각수인지 판별해 나가는 방법으로 답을 찾는 것이다. 예를 들면, (1, 5)가 있는 오각수 리스트에 다음 오각수인 12를 추가하고, 기존 오각수와 차이 11(12-1), 7(12-5)을 차례로 오각수인지 확인하고 만약 오각수인 경우 두 수의 합이 오각수인지 검증한다.

많이 비효율적이지만 답을 구했던 것 같고, 오각수인지 판별하는 것에는 33번 문제를 해결할 때 잠깐 언급했던 근의 공식을 이용해서 오각수 공식 P_n=n(3n−1)/2을 n 기준으로 바꾸면, n=(1+(1+24p)**0.5)/6이 된다. 이것을 활용하여 간단하게 확인 가능하다.

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자리 숫자를 잘라내어 검증하는 형태로 구성했었다.

The nth term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

삼각수 수열의 n번째 항은 t_n = ½n(n+1)이다. 따라서, 처음부터 열번째까지 삼각수는 다음과 같다:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

단어에 있는 각 글자를 알파벳 순서대로 번호를 매겨 값을 더하여 단어값을 구하게 된다. 예를 들어, SKY의 단어값은 19+11+25=55=t₁₀이다.단어값이 삼각수이면 그런 단어를 삼각 단어라 부른다. 

If the word value is a triangle number then we shall call the word a triangle word.

거의 2천개 영어단어가 있는 16K 크기의 문서 파일인 words.txt (우클릭하고 "(으)로 링크 저장")에는, 몇 개의 삼각수가 있는가?

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

파일을 읽어, 단어로 리스트를 구성하고, 각 단어를 읽어서 그 단어가 삼각수이면 카운트를 1씩 추가하는 것이 중심 알고리즘이다. 참고로, 삼각수는 12번 문제에서 한 번 나왔던 개념이다.

이를 구현하기 위해서는 파일을 열어 읽은 내용을 따옴표를 제외하고 문자열을 만드는 것이 첫번째이고, 딕셔너리를 이용해서 각 단어의 단어값을 구하는 것이 두번째이다. 삼각수 여부를 검증하는 것이 필요한데, 가장 긴 단어에 단어길이x26(Z의 값)까지 삼각수를 구한 다음에 각 단어의 단어값이 삼각수 리스트에 있는지 비교하는 방법으로 구현하였다.

삼각수 여부 검증하는 것을 달리 생각해보면 근의 공식을 활용하여 구할 수도 있다. n번째 항을 구하는 공식을 n을 기준으로 근의 공식을 적용하면 n=(-1+(1+8t_n)**0.5)/2가 된다. 원래는 +-이지만 이미 -1이 있는데 또 빼면 음수가 되므로 +인 경우만 계산하면 된다. 이렇게 해서 나오는 n이 자연수인 경우 그 단어는 삼각 단어가 되는 것이다.

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에서 시작하여 내려오면서 가장 먼저 나오는 소수가 해답이 되므로, 훨씬 빠른 시간에 답을 구할 수 있을 것이다.

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12^th digit of the fractional part is 1.

If d_n represents the n^th digit of the fractional part, find the value of the following expression.

d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000

무리수인 10진 분수는 양의 정수를 연결하여 만들어진다:

0.123456789101112131415161718192021...

분수 부분의 12번째 자리 숫자는 1이다.

만약 d_n 이 분수의 n번째 자릿수를 나타낸다면, 다음 표현식의 값을 구하시오.

d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000

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

위 특성을 가지는 숫자를 문제 제목인 챔퍼나운 수(Champernowne's constant)라고 부른다고 한다.

1부터 계속 커지는 숫자를 붙여나가는 문자열을 만들면서 1, 10, 100, 1000, 10000, 100000, 1000000번째 숫자를 구하고 그 값을 모두 곱하면 되는 문제이다. 구현하는 방법은 다양하겠지만 프로젝트 오일러 문제를 차례대로 풀어왔다면 그렇게 어렵지 않게 해결 가능한 문제이다.

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

각 면이 정수 길이 {a, b, c}를 가지는 직각 삼각형의 둘레를 p라고 하면, p가 120일 때 정확하게 3가지 경우({20,48,52}, {24, 45, 51}, {30,40,50})만 있다.

p ≤ 1000일 때 p가 얼마인 경우에 가장 많은 경우의 직각 삼각형이 가능한가?

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

직각 삼각형의 속성으로는 a²+b²=c²가 있고, 문제에서 p=a+b+c로 되어 있는 전제 조건을 이용하여 해결해야 한다.

가장 긴 변을 c라고 할 때, a와 b는 같을 수도, 다를 수도 있다. 이 중 b가 더 클 수 있다고 생각하면 a≤b 관계가 생긴다. 그리고, c는 피타고라스의 정리에 의해 어떤 형태로든 a, b 보다는 크게 된다. 설정한 관계대로 정리하면 a≤b<c가 된다. 세 숫자가 모두 자연수인 직각삼각형 중 가장 작은 것은 3, 4, 5이고, 이것의 둘레는 12이다. 그리고, 보수적으로 계산해도 a, b 두 숫자 중 하나의 크기는 전체 둘레길이의 절반이 될 수 없다.

b를 기준으로 4부터 499까지 반복하면서, b보다 같거나 작은 a를 1부터 b까지 반복해서 피타고라스 정리에 따라 c를 구하고, c가 자연수이고, a+b+c가 1000이하인 경우를 모으면 된다.

Take the number 192 and multiply it by each of 1, 2, and 3:

    192 × 1 = 192
    192 × 2 = 384
    192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

192를 1, 2, 3으로 곱하면 다음과 같다:

    192 × 1 = 192
    192 × 2 = 384
    192 × 3 = 576

각 결과물을 연결시켜 보면 1에서 9 pandigital인 192384576을 구할 수 있다. 192384576을 192와 (1, 2, 3)의 연결된 곱(concatenated product)으로 부른다.

9를 1, 2, 3, 4, 5로 곱해서 연결하면 1에서 9 pandigital인 918273645가 되며, 이것은 9와 (1, 2, 3, 4, 5)의 연결된 곱이다.

1보다 큰 자연수(1, 2, ..., n)으로 만들 수 있는 연결된 곱 중 가장 큰 9자리의 1에서 9 pandigital은 무엇인가?

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

문제에서 n을 2 이상으로 한정했기 때문에 5자리 숫자는 최소 10자리가 되어서 1에서 4자리 숫자의 범위 내에서 찾으면 되는 것을 알 수 있다.

숫자에 1, 2, 3 등을 차례로 곱하면서 나온 결과물을 연결한 길이가 9인 경우(10 이상이면 다음 숫자로), 9자리 숫자에 1~9까지 숫자가 하나씩 있는지 확인하는 것을 반복하면 된다.  결과로 나온 값을 정렬해서 가장 큰 수를 구하면 되기 때문에 보기 보다는 어렵지 않게 해결할 수 있다.

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 decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

10진수 585는 2진수 1001001001₂ 이며 2진수, 10진수에서 모두 회문이다.

백만 이하의 숫자 중에서 10진수, 2진수로 모두 회문인 숫자의 합을 구하시오.

(2진수, 10진수 모두에서 회문은 0으로 시작되지 않는 것에 주의하시오)

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

4번 문제에서 나왔지만 회문은 앞, 뒤 양쪽에서 읽었을 때 같은 것을 이야기하는데, 이번 문제는 2가지 진법에 대해 적용하게 되어 있어 난이도가 좀 더 높아졌다.

주의사항에서 0으로 시작되지 않는다고 했기 때문에 10진수에서 짝수이면 2진수에서 0으로 끝나고 회문으로 만들면 0으로 시작하기 때문에, 홀수만 대상으로 회문을 확인하면 된다.

10진수를 2진수로 바꾸는 것은 내장함수 bin()을 활용했는데, 이렇게 하면 0b로 시작되는 결과값이 나오기 때문에 회문을 판별할때는 0b를 제외하기 위해 2진수의 3번째 자리부터 회문여부를 판별하면 된다.

효율적이지는 않지만 문제에서 요구한 내용에 따라 답을 구할수는 있다.

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가 있으면 소수가 아닌 것으로 보고 다음 숫자로 넘어가게 할 수 있다.

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: As 1! = 1 and 2! = 2 are not sums they are not included.

1! + 4! + 5! = 1 + 24 + 120 = 145이기 때문에, 145는 재미있는 숫자이다.

각 자리 숫자의 계승(팩토리얼)의 합과 동일한 모든 숫자의 합을 구하시오.

주의: 1! = 1과 2! = 2는 합계가 아니므로 포함되지 않는다.

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

각 자리수를 활용하는 문제가 많기 때문에 파이썬의 map을 이용하여각 자리 숫자를 리스트로 바꾸고, 리스트를 다시 숫자로 바꾸는 것이 매우 유용하였다.

이 문제에서도 상한이 없기 때문에 먼저 정리하는 것이 필요한데, 9!이 362880이기 때문에 9가 8번 반복되더라도 그것을 합하면 29030400이 되는 것을 감안하면 7자리 숫자 내에 답이 있는 것을 알 수 있다. 0!=1인 것까지 고려하여 매번 팩토리얼 계산에 시간을 낭비하지 않도록 팩토리얼 결과값을 리스트로 만들어서 활용하였다.

문제를 해결하는 로직은 간단한데, 숫자가 크기 때문에 시간이 많이 소요되었다.

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

분수 49/98은 경험이 적은 수학자가 잘못된 방법을 믿고 9를 지우는 방법으로 단순화시켜도 49/98=4/8은 맞게 되는 신기한 분수이다.

30/50=3/5와 같은 분수는 흔한 예시로 생각하자.

이런 유형의 분수에서 분자와 분수가 2자리 숫자이고 1 미만의 값이 되는 흔하지 않은 예시는 정확하게 4가지가 있다.

이 4가지 분수를 곱해서 약분했을 때, 분모의 값을 구하시오.

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

2자리 숫자 분자, 분모에서 공통된 숫자를 하나 지웠을 때 지우기 전의 숫자와 값이 동일한 것을 4개 찾는데, 제약사항으로 지우는 숫자는 0이 아니고, 남은 두 수가 같거나 분자에 있는 수가 커서도 안된다.

분자는 11~98, 분모는 분자+1~99까지 반복하면서 나온 분수에서 동일한 수가 있으면, 그 수를 삭제하고, 남은 수와 애초의 분수가 동일한 분수 4개를 찾고, 분수 4개를 곱한 후, 약분해서 구하면 된다. 이 경우 지우는 숫자가 0이 안되도록 처리해 주는 부분이 추가로 필요하다.

조금 더 빨리 계산하려면, 공통되는 수 1자리, 분자 나머지 1자리, 분모 나머지 1자리를 대상으로 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, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

1부터 n까지 숫자가 각 자리에 한 번씩 사용되었으면 그 n자리 숫자를 pandigital이라 부른다. 예를 들어, 5자리 숫자 15234는 1에서 5 pandigital이다.

7254는 39x186=7254로 승수, 피승수, 곱이 1에서 9 pandigital이므로 특이하다.

승수/피승수/곱이 1에서 9 pandigital인 숫자의 곱의 합을 구하시오.

힌트: 어떤 곱은 한 가지 이상의 방법으로 구할 수 있는데 합계에서 한 번만 포함되어야 한다.

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

pandigital이라는 단어는 처음 보는데 검색해봐도 한글로 대응되는 단어가 나오지 않았다.

간단히 생각하면 1~98765432까지 승수와 피승수를 이중으로 반복하면서 곱을 구해서 승수, 피승수, 곱이 1에서 9 pandigital인지 판정하고, 곱의 중복을 제거하여 더하면 된다. 하지만, 불필요한 계산이 많이 포함되어 시간이 엄청 오래 걸리므로 좀 더 빠른 속도로 구할 수 있는 개선방안이 필요하였다.

'승수x피승수=곱' 관계에서 예시는 2자리x3자리=4자리인 경우이다. (3자리x2자리=4자리와 같이 동일한 결과가 나올 경우를 제외하고) 이 외에 가능한 경우를 생각해 보면, 1자리x4자리=4자리 밖에 없다.

승수가 1자리이고 피승수가 4자리인 반복문과 승수가 2자리이고 피승수가 3자리인 반복문에서 pandigital 숫자 여부를 판정하고, 결과를 집합으로 변형하여 중복을 제거하고 합계를 구하였다.

pandigital 숫자 여부를 판정하는 것은 승수/피승수/곱의 자리수를 확인하고 합집합을 만들어서 1~9가 있는 집합과 동일한지 비교하거나, 1~9가 있는 집합에서 승수, 피승수, 곱의 차집합을 차례로 구해서 null이 되는지 확인하는 등 개인 성향에 따라 여러가지 방법이 가능할 것이다.

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:

    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

영국의 화폐에는 파운드(£)와 펜스(p)가 있다. 통용되는 동전에는 다름 8가지가 있다:

    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

2파운드는 다음 방법으로 만들 수 있다.

    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

동전을 이용하여 2파운드를 만드는 방법에는 몇가지가 있는가?

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

재귀함수 형태도 가능할 것 같았는데, 큰 화폐부터 시작해서 8번 중첩되는 반복문(for loop)을 구성해서 값이 200이 되면 카운트를 증가시키고 다음 단계로 넘어가는 형태로 해결했다.

좀 더 빨리 실행시키기 위해서는 반복되는 계산을 줄이기 위해 이전 반복을 기억하게 하는 메모이제이션, 접근을 다르게 해서 해결하는 동적 프로그래밍 방법이 있다고 하는데 이해하기에는 좀 어려웠다.

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

놀랍게도 각 자리 숫자의 4제곱 숫자의 합으로 표현될 수 있는 숫자는 4개 밖에 없다:

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

1 = 1⁴ 은 합계가 아니기 때문에 포함하지 않았다.

이 숫자의 합은 1634 + 8208 + 9474 = 19316이다.

각 자리 숫자의 5제곱 숫자의 합으로 표현 가능한 숫자의 합계를 구하시오.

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

파이썬에서 숫자를 각 자리 숫자의 리스트로 변환하는 방법(반대로 숫자 리스트를 모아 하나의 숫자로 만드는 방법)을 알게 되면서 이런 유형의 숫자를 조작하는 문제는 구현하는 방법에만 집중할 수 있게 되었다.

1은 제외한다고 했으니, 2부터 시작해서 각 자리 숫자를 분리해서 5제곱 값을 구하고 이들을 합하여 원래 숫자와 동일한 것을 찾으면 된다.

핵심 알고리즘은 간단한데, 여기서 생기는 고민거리는 문제에서 모두 구하라고 했지 상한선을 제시하지 않았기 때문에 그것을 찾는 것이다. 가장 큰 경우인 9의 5제곱은 59049이고, 6자리 숫자 모두 9인 경우인 354294가 이론적인 상한이 되므로 2부터 354294이내의 숫자를 대상으로 위 알고리즘을 적용하면 구할 수 있다.

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

    2²=4, 2³=8, 2⁴=16, 2⁵=32
    3²=9, 3³=27, 3⁴=81, 3⁵=243
    4²=16, 4³=64, 4⁴=256, 4⁵=1024
    5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

2 ≤ a ≤ 5이고 2 ≤ b ≤ 5인 a^b 의 모든 자연수 조합은 다음과 같다:

    2²=4, 2³=8, 2⁴=16, 2⁵=32
    3²=9, 3³=27, 3⁴=81, 3⁵=243
    4²=16, 4³=64, 4⁴=256, 4⁵=1024
    5²=25, 5³=125, 5⁴=625, 5⁵=3125

중복되는 경우를 제거하고 숫자 순서대로 정리하면 다음 15개의 유일한 요소 수열이 된다:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 ≤ a ≤ 100이고 2 ≤ b ≤ 100일때 a^b 로 만들어지는 수열에는 몇 개의 유일한 요소가 있는가?

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

a와 b를 각각 2~100까지 반복하는 중첩되는 반복문을 통해 a^b 목록을 구하면 되는 문제이다. 100의 100승이면 매우 큰 수인데 파이썬으로 구현하고 있기 때문에 고려하지 않아도 되었다.

하나 추가로 고려할 것이 중복되는 숫자를 어떻게 제거할 것인가인데, 파이썬 환경에서 2가지 방법이 가능할 것으로 생각되었다. 하나는 반복문 안에서 a^b 를 구했을 때 결과 목록에 없으면 추가하는 방법이고, 다른 하나는 전체 목록을 구한 다음에 집합으로 자료형을 변환해서 중복을 자동으로 제거하게 만드는 것이다.

집합 자료형을 활용해 보고 싶어서 전체 목록을 구한 후에 집합으로 변환해서 중복을 제거하고, 결과값 갯수를 구하는 방법으로 해결하였다.

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

1에서 시작해서 오른쪽 시계방향으로 움직이는 5x5 크기의 나선형은 다음과 같다:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

대각선에 있는(굵게 표시된) 숫자의 합은 101로 판명된다.

1001x1001 크기의 나선형에서 대각선에 있는 숫자의 합은 얼마인가?

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

5x5 나선형 표를 보면서 발견한 규칙은 대각선에 있는 숫자가 3x3일때는 2씩 커지고, 5x5일때는 4씩 커진다. 규칙성을 찾아보면 대각선에 있는 숫자가 7x7일때는 6씩, 9x9일때는 8씩 커지게 됨을 유추할 수 있다.

처음은 1, 두번째는 2씩 커지는 숫자를 4번, 세번째는 4씩 커지는 숫자를 4번, 그 다음은 6씩 커지는 숫자를 4번 더해나가는 형태로 1001x1001 크기까지 반복하면 대각선에 있는 숫자의 합을 구할 수 있다.

규칙만 발견하면 그리 까다롭지 않은 문제이다. 4번씩 더하는 것이 반복되는 것을 개선할 방법이 있을까 싶어서 크기별 대각선 숫자의 합계에 대한 규칙성이 있는가 생각해 봤는데 찾지 못해서 위 방법으로 해결했다.