책 이야기

프로젝트 오일러 문제를 100번까지 시도했는데, 이 중 (직접 풀어 해결한 79번 포함한) 72개를 풀었고, 28개 문제는 아직 해결하지 못했다. 남은 문제를 난이도 기준으로 보면, 난이도 5% 문제 2개(26, 59번), 10% 문제 4개(54, 69, 76, 81), 15% 문제 3개(51, 65, 85), 20% 문제 7개(60, 61, 64, 70, 72, 80, 82), 25% 문제 5개(66, 68, 77, 83, 96), 30% 문제 2개(78, 100), 35% 문제 4개(84, 86, 93, 98), 40% 문제 1개(88)이다.

바로 해결하지 못한 문제만 남았기에 시간이 많이 필요할 수도 있을 것 같지만, 일단 100번까지는 모두 해결하는 것을 목표로 계속 시도해봐야겠다.

파이썬을 익히기 위해 시작한 프로젝트 오일러인데, 이제는 수학공부를(특히나 정수론) 더 많이 한다는 느낌이긴 한데, 그래도 프로젝트 오일러 덕분에 파이썬 기반으로 파일 읽고 쓰기, 자료형 변환과 활용, 함수 활용, 모듈 사용 등을 편하게 활용가능하게 되었다. 하지만, 람다 표현식, 클래스, 제너레이터, 정규표현식 등 좀 더 파이썬스럽게 프로그래밍하기 위해 필요한 부분은 문제 해결에 잘 활용되지 않고, 아직도 체계적으로 이해하지 못하고 있는 것 같다.

그리고, 문제 해결하기 위해 작성한 코드가 파이썬이라기 보다는 C와 같은 전통적인 프로그램 형태에 가깝기 때문에 소스코드 없이 어떤 로직(내지는 알고리즘)이 필요한지만 기록하는 형태로 계속 정리할 생각이다.

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까지만 계산하면 되는 것이었다. 그렇게 코드를 수정하고 나서 정답을 구할 수 있었다.

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

(3453의) 세제곱 수인 41063625는 다른 두 세제곱 수인 56623104 (3843의 세제곱), 66430125 (4053의 세제곱)을 만들어 내도록 바뀔 수(순열을 만들 수) 있다. 실제로, 41063625는 그 자릿수로 세제곱 수인 3개의 순열을 만들 수 있는 가장 작은 수이다.

그 자릿수로 5개의 세제곱 수인 순열을 만들 수 있는 가장 작은 세제곱 수는 무엇인가.

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

가장 간단한 접근은 한 숫자의 세제곱 수를 구하고, 순열을 만들어서 4개 이상의 세제곱 수가 있는 가장 작은 수를 구하는 것이다.

이렇게 할 경우 세제곱 수에 대한 순열을 만들고, 이들 중 세제곱 수가 몇 개인지 검증하는데 많은 시간이 소요될 것으로 예상되어 접근을 다르게 해보기로 했다. 1부터 커가면서 세제곱 수를 만들고, 거기에 있는 자릿수를 정렬하여, 이전의 (정렬된) 세제곱 수 중 그 값과 같은 것이 4개 이상인 것을 찾는 방식으로 접근해 봤다. 논리는 조금 허술한 것 같았는데, 늦지 않는 시간에 정답을 구할 수 있었다.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

1에서 시작해서 반시계 방향으로 회전하는 정사각형을 구하면 한 변의 길이가 7인 것은 다음과 같다.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

흥미롭게도 오른쪽 아래쪽 대각선에는 제곱수가 놓이고, 더욱 흥미있는 것은 두 대각선에 있는 13개 숫자 중 소수는 8개이며, 비율은 8/13≈ 62%이다.

회전하면서 둘러싸는 새로운 층을 만들면, 한 변의 길이가 9인 정사각형을 만든다. 이 과정이 계속될 때, 두 대각선에 있는 숫자 중 소수의 비율이 10% 이하가 되는 것은 언제인가?

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

1에서 오른쪽 아래에 대각선 방향에 있는 9, 25, 49, ... 는 제곱수이므로 소수가 아니다. 사각형이 커질 때마다 새롭게 검증 대상이 되는 숫자는 처음의 3, 5, 7, 두번째 13, 17, 21의 세 숫자씩이 된다.

대각선에 추가로 포함되는 3개 숫자 중 소수를 판별하고, 대각선 숫자 중 소수의 비율을 구하면 되므로 그렇게 까다롭지 않게 해결 가능하다.

루트2는 무한하게 반복되는 분수로 표현될 수 있다.

처음 4번의 반복을 확장하면 위 그림과 같다:

다음 3번 확장은 99/70, 239/169, 577/408이지만, 8번째 확장은 1393/985이며 분자의 자릿수가 분모 자릿수보다 크게 되는 첫 숫자이다.

처음 1천번 확장에서 몇 개의 분수에서 분자가 분모보다 자릿수가 더 큰가?

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

이 문제에서 루트2를 구하는 과정을 잘 이해했으면, 뒤에 연계되어 나오는 연분수 문제들을 쉽게 해결할 수 있었는데 너무 기계적으로 간단하게 해결해버렸다.

가만히 살펴보면 분모는 직전 분모x2와 2번 직전 분모를 합한 값이며, 그 때 분자는 1을 빼면 직전 분모 값이 되는 것이 보였다. 예를 들어, 3/2, 7/5 다음 수의 분모는 5x2+2=12이며, 분자는 1을 제외하면 5가 되므로 1+5/12=17/12가 된다.

이 과정을 반복하면서 자릿수가 차이나는 경우를 찾는 것으로 간단하게 해결되었다.