책 이야기

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가 된다.

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

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에 순차적으로 대입해서 나온 결과의 각 자릿수를 더하는 것으로 어렵지 않게 구할 수 있다

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

47의 순서를 반대로 하여 더하면 나오는, 47+74=121은 회문이다.

모든 숫자가 회문을 이렇게 빨리 생성하지 않는다. 예를 들면, 다음과 같다.

    349 + 943 = 1292,
    1292 + 2921 = 4213
    4213 + 3124 = 7337

즉, 349는 회문이 되기 위해 3번 반복이 필요하다.

비록 아직 아무도 증명하지 않았지만, 196 같은 숫자는 절대로 회문을 생성하지 않는 것으로 생각되고 있다. 숫자를 반대로 하고 더하는 숫자를 반복해도 회문을 만들지 못하는 숫자를 라이크렐(Lychrel) 수 라고 한다. 이들 숫자의 이론적인 특성과 이 문제의 목적을 위하여, 다른 방법으로 증명되지 않은 숫자를 라이크렐 수로 가정한다. 추가로, 주어진 1만 이하의 숫자 모두는 (1) 50번 이하의 반복으로 회문이 되거나, (2)  보유한 계산 능력을 활용하여도 회문으로 만들지 못한 것이다. 실제로, 10677은 회문을 만들기 위해 50회 이상의 반복이 필요한 첫 숫자이다: 4668731596684224866951378664 (53회 반복, 28자리 수)

놀랍게도, 회문인 숫자이지만 자신은 라이크렐 수인 숫자가 있다: 첫 예시는 4994이다.

1만 이하의 숫자 중에 몇 개의 라이크렐 수 가 있는가?

주의: 라이크렐 수의 이론적 특성을 강조하기 위해 2007.4.27일 단어가 일부 수정되었다.

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

문제가 어렵다기 보다는 문제를 이해하기 어려웠던 문제였다. 복잡하고 길게 쓰여있지만, 문제에서 요구한 것은 숫자를 반대로 하여 더하는 과정을 50번 반복할 때까지 회문이 되지 않는 경우를 라이크렐(Lychrel) 수라 하고, 1만 이하의 숫자 중 라이크렐 수가 몇 개인지 구하는 것이다.

숫자의 순서를 반대로 하고 두 숫자를 더하는 부분과 특정 숫자가 회문인지를 판별하는 부분을 작성하면, 1만까지 반복하면서 회문이 구해지지 않는 라이크렐 수가 몇 개인지 찾으면 되기 때문에 오일러 프로젝트를 여기까지 풀었으면 그리 어렵지 않게 해결 가능하다.