책 이야기

2⁷=128은 "12"로 시작하는 첫번째 2의 거듭제곱수이며, "12"로 시작하는 다음 2의 거듭제곱수는 2⁸⁰ 이다.

p(L,n)을 L로 시작하는 십진수 중 2^j가 n번째 가장 작은 j를 나타낸다고 정의하면, p(12,1)=7이고 p(12,2)=80이다.

또한 p(123,45)=70이다.

p(123,678910)을 구하시오.
--------------------------------------------------------------------------

문제에서 요구하는 대로 구성하면 프로그램의 구조는 간단하다. 2를 계속 곱해가면서 L로 시작되는 n번째 숫자를 찾아 거듭제곱수를 알려주면 된다.

이렇게 구현하면 예시로 나와있는 p(12,1), p(12,2), p(123,45)는 어렵지 않게 구할 수 있다. 하지만, 2의 거듭제곱수 중에서 123으로 시작하는 678910번째 숫자가 2의 몇 거듭제곱인지 찾는 것은 데이터 허용범위가 넓은 파이썬으로도 어려운 일이었다. (이번에는 4300자릿수 이상을 넘을 수 없다는 에러메시지를 봤던 것 같다)

프로젝트 오일러의 높은 번호 문제는 난이도가 낮아도, 간단히 해결 가능한 것이 아니라 (주로 상상도 못한 크기의 숫자로) 한계가 숨어 있고, 이것을 어떻게 해결해내는 것인지가 추가로 포함되어 있는 것 같다.

이번 문제에서는 앞의 3자리만 동일하면 되기 때문에, 일정크기 이상으로 커지면 앞의 3자리에 영향을 미치지 않을 아랫쪽 수를 10000으로 나눠 없애는 형태로 계산했는데, 정확한 숫자를 구하는 것이 아니어서 살짝 걱정되었지만 맞출 수 있었다.

512는 각 자리수의 합을 거듭제곱한 것과 같다는 점에서 재미있는 수이다: 5+1+2=8이고 8³=512이다.

이러한 속성을 가진 다른 수는 614656=28⁴이다.

an을 이런 수열의 n번째 숫자라고 정의하고,  a_n은 두자리 이상의 숫자가 되어야 한다.

a₂=512이고 a₁₀=614656임을 알려준다.

a30을 찾으시오.

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

처음에는 brute force에 가까운 방법으로 접근했는데, 시간 문제가 생겼다. 즉, 10부터 1씩 키워나가며 자리수의 합을 구하고, 자리수의 합에 대해 거듭제곱을 하면서 원래 숫자가 만들어지는지 확인하는 방법이었는데, 예시로 제공한 10번째 숫자까지는 비교적 빠른 시간 내에 구했지만, 그 이후로는 숫자가 기하급수적으로 커지면서 10분 이상이 지나도 답이 나오지 않는 상황이 되었다.

그래서, 다른 사람은 어떤 식으로 접근했는지 찾아봤는데, 파이썬이 큰 수를 다루는 데 유리한 점을 이용하여 해결했다는 것이 있어서 그것을 참조해서 해결했다. for 반복문 2개를 이용해서 일정크기 이내의 밀과 지수에 대한 거듭제곱을 만들어서, 거듭제곱 각 자리수의 합이 밑과 동일한 경우를 구하는 방법이다. 그 이후에는 정렬하고, 30번째 요소를 찾으면 되는 것이다.

만약, 찾은 것이 정답이 아니면 밑을 충분히 크게 만들지 않았기 때문에 밑의 반복범위를 키우고, 그래도 안되면 거듭제곱의 반복범위를 키우는 방법으로 접근하면 어렵지 않게 구할 수 있을 것이다. 생각하기에 따라 상당히 위험한 방법의 brute force이지만 파이썬이 큰 숫자를 다루는 데 문제가 없기에 가능한 방법이었던 것 같다.

r을 (a-1)ⁿ+(a+1)ⁿ을 a²으로 나누었을 때 나머지로 하자.

예를 들어, a=7이고 n=3일 때, r=42가 된다(6³+8³=728≡42 mod 49). 그리고 n 값이 바뀌면 r도 바뀌게 된다. 하지만, a=7일 때 r의 최대값인 r_max=42이다.

3≤a≤1000일 때, r_max의 합계(∑r_max)를 구하시오.

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

어렵지 않아 보이지만 실행 시간이 많이 소요되는 문제이다. 나누는 수가 a²이기 때문에 나머지를 확인하기 위해 검증하는 범위를 a²번까지 설정해야 했기 때문이다.

그리고, 나머지 함수의 특성을 살려서 적용해야지 문제에서 제시한 그대로 코딩했을 때에는 숫자가 기하급수적으로 커지면서 실행시간이 매우 많이 필요하게 되었다.

나머지 함수의 곱셈 특징((a*b)%c=(a%c)*(b%c))을 활용하여, 거듭제곱의 경우 분산해서 계산하도록 코드를 개선했다. 즉, a⁷=a*a²*a⁴, a⁹=a*a⁸과 같은 형태로 나누고, 각각에 나머지 함수를 적용해서 숫자가 최대한 커지지 않도록 만들었다.

그렇게 개선했어도 실행시간은 많이 필요했으며(100까지 7초, 200까지 58초, 300까지 173초, 400까지 360초, 500까지 628초, 600까지 942초, 700까지 1365초, 800까지 1777초, 900까지 2415초, 1000까지 3043초로 총 3시간 필요), 이 방식보다는 좀 더 빠른 형태의 수학에 기반한 해법이 있을 것 같다.

Comparing two numbers written in index form like 2¹¹ and 3⁷ is not difficult, as any calculator would confirm that 2¹¹ = 2048 < 3⁷ = 2187.

However, confirming that 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

지수로 표현된 두 수 2¹¹과 3⁷을 비교하는 것은 어렵지 않다. 계산기를 이용하면 2¹¹ = 2048 < 3⁷ = 2187을 확인할 수 있다.

그러나, 3백만 자릿수 이상이 되는 두 수가 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ 인 것을 확인하는 것은 상당히 어렵다.

1천 개 이상의 밑과 지수 쌍이 각 행에 있는 22K 크기의 텍스트 파일 base_exp.txt (오른쪽 클릭하고 다른 이름으로 링크 저장) 중 가장 큰 값을 가지는 숫자를 찾으시오.

주의: 파일의 첫 두 줄은 위의 예시에 있는 숫자이다.

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

정직하게 프로그래밍 했더니 역시나 OverflowError: math range error라는 에러메시지를 보게 되었다. 급격하게 커지는 지수를 따라가지 않고 계산할 방법은 이제는 까맣게 잊어버린 log를 다시 찾아보는 방법밖에 없어 보인다.

로그의 지수법칙(loga^b=bloga)을 이용하여 동일한 밑인 상황에서 base_exp 파일의 밑과 지수를 로그에 대입하면(문제의 예시에서 518061*log632382와 525806*log519432를 비교하는 형태) 어렵지 않게 해결 가능하다.

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

    28 = 2² + 2³ + 2⁴
    33 = 3² + 2³ + 2⁴
    49 = 5² + 2³ + 2⁴
    47 = 2² + 3³ + 2⁴

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

소수의 제곱, 세제곱, 네제곱의 합계로 구할 수 있는 가장 작은 수는 28이다. 실제로, 소수의 제곱, 세제곱, 네제곱을 합하여 구할 수 있는 50이하의 수는 다음과 같이 4가지가 있다:

    28 = 2² + 2³ + 2⁴
    33 = 3² + 2³ + 2⁴
    49 = 5² + 2³ + 2⁴
    47 = 2² + 3³ + 2⁴

소수의 제곱, 세제곱, 네제곱의 합으로 구할 수 있는 5천만 이하의 숫자는 몇가지인가?

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

문제 난이도는 20%로 높게 책정되어 있지만, 그동안 많이 다뤄왔던 소수의 연장선에 있고 파이썬이 큰 숫자를 쉽게 다룰 수 있게 지원하기 때문에 그렇게 어렵지 않게 해결할 수 있었다. 문제 난이도를 생각하면 좀 더 빠르게 해결가능한 방법이 있을 것 같았지만, 문제에서 요구하는 정석대로 접근해서 해결했다.

5천만 이하의 소수의 제곱, 세제곱, 네제곱을 구하고, 이것을 반복문을 통해 서로 더해나가면 어렵지 않게 구할 수 있다.

처음에, 문제에 있는 prime을 간과한 덕분에 모든 자연수의 제곱, 세제곱, 네제곱을 구하고, 반복문을 통해 더한 것을 모두 나열하니 1.47억개의 리스트가 나왔고, 여기에서 중복을 제거하려 하니 몇시간이 걸려도 답이 나오지 않는 상황이 발생했다.

문제를 다시 읽어보니 소수를 대상으로 하는 것이어서 제곱, 세제곱, 네제곱이 훨씬 적게 되고, 마지막에 중복을 제거하지 않고 집합 자료형을 이용하여 중복을 제거하면서 합을 구했더니 훨씬 간단한 로직으로 구할 수 있었다.

The 5-digit number, 16807=7⁵, is also a fifth power. Similarly, the 9-digit number, 134217728=8⁹, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

5자리 수인 16807은 또한 5제곱 수이기도(7⁵) 하다. 비슷하게, 9자리 수인 134217728은 9제곱 수이다(8⁹).

n자리 제곱수이기도 한 n자리 양의 자연수는 몇 개 있는가?

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

숫자에서 범위를 명확하게 얘기하지 않아 고민하는 시간이 필요했다. 답을 구하는 알고리즘 자체는 각 숫자의 제곱수를 구해서(5의 경우 5, 25, 125, 625, ...), 각 숫자가 각 자리의 제곱수에 해당하는지 확인하면 된다. 예로 든 5의 경우 5의 1제곱은 5이므로 1자리 수, 5의 2제곱은 25로 2자리 수, 5의 3제곱은 125로 3자리 수이지만, 5의 4제곱은 625로 4자리 수가 아니다.

처음에는 n자리를 한자리 수로 생각해서 9의 9제곱까지만 구했는데 정답이 아니었다. 곰곰히 생각해 보니 상한을 두지 말고 구해야 하는 것이었고, 밑에 해당하는 숫자는 10의 1승은 2자리 수(10)이므로 9까지만 계산하면 되는 것이었다. 그렇게 코드를 수정하고 나서 정답을 구할 수 있었다.

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

구골(10¹⁰⁰)은 100개의 0이 필요한 매우 큰 수이다. 100¹⁰⁰ 은 200개의 0이 필요한 거의 상상할 수 없는 큰 수이다. 크기에도 불구하고 각 자리 숫자의 합은 겨우 1이다.

a, b가 100보다 작고 a^b인 자연수가 있을 때, 각 자릿수 합계의 최대값은 얼마인가?

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

매우 큰 수를 다루는 문제이기 때문에 다른 언어에서는 고려할 요소가 많이 생길 것이지만, 파이썬에서는 문제에서 요구하는 절차를 충실하게 따르면 해결가능한 문제이다.

100미만의 수를 a, b에 순차적으로 대입해서 나온 결과의 각 자릿수를 더하는 것으로 어렵지 않게 구할 수 있다

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자리 숫자를 구하면 되기 때문에 정답자가 많은 것 갈다.

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 를 구했을 때 결과 목록에 없으면 추가하는 방법이고, 다른 하나는 전체 목록을 구한 다음에 집합으로 자료형을 변환해서 중복을 자동으로 제거하게 만드는 것이다.

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

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

2¹⁵ = 32768이고, 각 자리 숫자의 합은 3 + 2 + 7 + 6 + 8 = 26이다.

2¹⁰⁰⁰ 각 자리 숫자의 합은 얼마인가?

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

2의 1000승은 매우 큰 수이지만 파이썬은 큰 수를 쉽게 다룰 수 있으므로 고려할 필요는 없고, 결과값의 각 자리 숫자를 어떻게 구할 것인지만 고민하면 되는 문제이다.

이 문제를 해결할 때에는 숫자, 리스트, 문자열 간 자료형 변환에 익숙하지 않아서 결과값을 10으로 계속 나누면서 나머지를 더하는 반복문으로 답을 구했다.