책 이야기

169와 961은 모두 소수의 제곱이다. 169를 반대로 하면 961이 된다.

다음 조건을 만족하면 reversible prime square(가역 소수 제곱)이라 부른다:

1. 회문(palindrome)이 아니며,
2. 소수의 제곱이며,
3. 반대로 한 것도 소수의 제곱이다.

169와 961은 회문이 아니며, 소수의 제곱을 반대로 한 것이다.

처음 50개 reversible prime square의 합계를 구하시오.

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

프로그램은 어렵지 않게 구성 가능한데, reversible prime square를 만족하는 숫자를 50개 찾는 것이 쉽지 않았다.

50개가 나올때까지 매번 소수를 추가로 만드는 경우 시간이 많이 소요될 것으로 보여서, 일정한 갯수의 소수와 소수의 제곱수 리스트를 먼저 만들어 놓고, 회문이 아니고, 순서를 반대로 한 것도 소수의 제곱수 리스트에 있는 것들을 따로 모으도록 구현했다.

100자리 중 2개, 1000자리 중 2개 등 생각보다 위 조건을 만족하는 숫자가 많이 나오지 않아서, 처음 소수를 만드는 갯수를 계속 키워가며 구해야 했다. 천만의 제곱까지 구해도 50개가 되지 않는다.

문제에서 요구한 조건을 만족하는 reversible prime square가 모두 홀수 자릿수의 숫자인 것은 의아했다. 확실한 이유가 생각되면 짝수 자릿수의 prime square는 검증과정을 생략하도록 해서 성능을 높을 수도 있을 것 같은데, 짝수 자릿수의 숫자가 없는 이유가 명확하게 떠오르지는 않아서 일단 모든 숫자를 대상으로 검증하게 했다.

일단 답은 구했지만 시간이 많이 걸렸다. 검색 끝에 찾은 몇가지 추가 조건은, △끝자리에 올 수 있는 수가 홀수이며 이 중 5의 배수인 5 제외, 1, 3, 7, 9의 제곱수는 1, 9이므로, 첫자리와 끝자리는 1, 9만 올 수 있으며, △첫자리에 1,9만 올 수 있으므로 제곱근은 1,3이 되고 이 경우 3자리 제곱은 5자리, 4자리 제곱은 7자리와 같이 홀수 자릿수로만 나오게 된다. 앞에서 얘기한 홀수 자릿수로만 reversible prime square가 나오는 이유를 알게 되었다.

그리고, 처음에는 소수의 제곱수 목록을 구해서(조건2) 그것을 대상으로 회문과 반대수를 구했는데(조건1,3), 제곱수를 구할 때 추가로 발견한 2가지 조건과 회문까지 판별해서 목록을 만들고(조건1,2), 반대수가 제곱수인 소수이면 정답 목록에 추가하는 방식으로 바꿔서 검증대상을 줄여봤다.

추가로 발견한 2가지 조건으로 검증대상이 500만개 이상에서 40만개 이하로 줄어 실행시간도 많이 개선되었지만, 검증대상 거의 마지막에 가서야 50개를 찾을 수 있어 실행시간은 여전히 필요했다.

회문인 숫자 595는 다음과 같이 연속된 제곱수의 합계로 나타낼 수 있다는 점에서 흥미롭다.

6²+7²+8²+9²+10²+11²+12²

천 이하에는 연속된 제곱수 합계로 나타낼 수 있는 회문이 11개 있고, 이들의 합계는 4164이다. 주의할 것은 1=0²+1²이지만 양의 정수의 합계를 고려하고 있으므로 해당하지 않는다.

10⁸(1억) 이하의 숫자 중에 회문이면서 연속된 제곱수의 합계로 나타낼 수 있는 숫자의 합을 구하시오.

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

회문은 4번 문제에서 처음 나온 이후에 오일러 프로젝트에 몇 번 나온 문제이고 여기까지 풀었으면 함수로도 가지고 있을 것이다.

일단 문제에서 요구한 대로 구현해 봤다. 1은 제외한다고 했으므로 2에서 1억까지 올라가면서 회문에 해당하는 숫자를 대상으로, 각 숫자가 연속된 제곱수의 합계로 나타낼 수 있는지 판별하는 것이다. 이를 위해 제곱수의 목록을 만들어두고 시작하는 자리를 이동해가면서 차례로 합해나가는 과정을 반복하도록 하고, 제곱수가 비교할 숫자보다 크면 그 수에 대해서는 검증을 중단하도록 했다.

실행해보니 처음에는 빠르지만 천만이 넘어가면서 실행속도가 엄청나게 느려지는 것이 보였다. 하지만 조금 기다려주면 끝이 나는 수준이어서 이렇게 해결하기로 했는데, 제곱수를 1억까지 만들었다가 그것이 넘는 경우가 필요해지면서 거의 마지막에 리스트의 인덱스 에러가 생기고 결과를 확인하지 못했다. 제곱수 리스트를 조금 더 크게 만든 후에 답을 구할 수 있었다.

하지만, 다른 사람은 어떻게 접근했는지 확인했을 때, 정반대로 접근하는 것이 있었는데 빠른 해결을 위해서는 좋은 방법 같아서 아이디어를 적는다. 접근을 반대로 해서, 1만의 제곱이 10억이므로, 1만 이하의 제곱수 목록을 만들고 각 숫자를  연속해서 나오는 결과 목록을 생성한 후에, 이 중 회문인 것만 답으로 선택하는 방법이다. 실험삼아 구현해봤는데, 결과 목록을 만드는 데 생각보다 많은 시간이 걸려 큰 차이가 나지 않을 것 같았다.

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 36². What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 96². We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

단어 CARE의 각 글자를 각각 1, 2, 9, 6으로 바꾸면 1296 = 36²의 제곱수가 된다. 여기서 주목할만한 점은, 동일한 디지털 교체 방법인 애너그램(anagram, 철자 순서 바꾸기)을 적용한 RACE 또한 9216 = 96²로 제곱수가 된다. CARE(와 RACE)는 제곱 애너그램 쌍이라 부르는데, 단어는 0으로 시작하지 않고 서로 다른 글자는 같은 디지털 값을 가지지 않도록 한다.

약 2천개 일반 영어 단어가 있는 16K 텍스트 파일인 words.txt (우클릭하고 다른 이름으로 저장)을 이용하여 모든 제곱 애너그램 쌍을 찾으시오 (회문 형태는 자신의 애너그램이 아니다).

이 쌍에서 구할 수 있는 가장 큰 제곱수는 무엇인가?

주의: 모든 애너그램은 제시된 텍스트 파일에서 구해야 한다.

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

문제를 해결할 때마다 드는 생각이지만, 요즘 언어 특성에 맞는 간결하면서도 빠른 접근방법이 있을 것 같은 느낌은 들지만 정확하게 모르기 때문에 정공법이라 할 수 있는 시간이 걸려도 단계별로 구현해 나가는 형태로 해결하고 있는 것 같다.

이 문제를 해결하려면, 일단 파일을 읽어 단어 리스트를 만들고, 그 중 애너그램이 될 수 있는 단어를 찾고, 단어 길이만큼의 제곱수 목록을 만들어서, 애너그램 후보 단어 그룹과 제곱수 목록이 매치되는 최대값을 찾는 4가지 과정이 필요했다.

파일을 읽어 단어 리스트를 만드는 것은 프로젝트 오일러 문제를 풀면서 몇 번 해봤기 때문에 기존에 작성한 것을 활용해서 따옴표만 처리해주면 되었다.

애너그램이 될 수 있는 단어를 찾기 위해, 각 단어를 알파벳 순으로 정렬했을 때 같은 값을 가지는 단어를 묶어 리스트를 만들었다.

제곱수 목록을 만들기 위해, 애너그램이 될 수 있는 단어들의 길이를 측정해서 최소 길이부터 최대 길이 사이에 있는 제곱수 목록을 만들었다. 조금 편하게 쓸 수 있을 것 같아 제곱수 목록을 단어 길이별로 만들었다.

애너그램 후보 단어 그룹과 제곱수 목록을 매치시키는 것을 구현하는 부분이 제일 어려웠는데, 실제 구현한 코드도 처음 생각한 모든 기능을 반영한 것은 아니지만 일단 정답을 맞췄기에 넘어가기로 했다. 문제의 예시로 설명하면, 4자리 제곱수의 1296, 애너그램 대상이 되는 CARE, RACE를 읽어서 애너그램 숫자 9216을 만들고 그것이 4자리 제곱수 목록에 있는지, 각 단어그룹을 해당 자리 제곱수 목록만큼 2중 반복문을 통해 찾도록 했는데 간단히 구현한 만큼 문제가 있었다.

SHEET, THESE의 경우 E의 자리 값이 같아야 되고, 그 값이 THESE로 되었을 때 같은 자리에 있어야 한다. SHEET의 숫자가 12334이면, THESE는 42313이 되어야 되는데 가지고 있는 실력으로는 그렇게까지 정교하게 만들어 낼 수가 없었다. 그래서 고민끝에 아이디어를 낸 것이 두 숫자의 종류가 같고, 같은 숫자 최대값이 애너그램의 같은 문자 최대값과 같은 경우로 조건을 추가했는데 답을 구할 수 있었다.

문제에서 요구한 기능을 모두 구현한 것은 아니지만 답은 구할 수 있어서 아쉽지만 기뻤다. 코드가 깔끔해지 못하지만 실행시간이 짧은 것은 의외였다.

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만까지 반복하면서 회문이 구해지지 않는 라이크렐 수가 몇 개인지 찾으면 되기 때문에 오일러 프로젝트를 여기까지 풀었으면 그리 어렵지 않게 해결 가능하다.

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번째 자리부터 회문여부를 판별하면 된다.

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

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

회문 숫자는 양쪽에서 읽어도 같다. 2자리 숫자 2개를 곱해서 나오는 가장 큰 회문은 91x99인 9009이다.

3자리 숫자 2개를 곱해서 만들 수 있는 가장 큰 회문은 얼마인가?

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

회문을 판별하기 위해서는 숫자 자료형으로는 어렵고, 문자열이나 리스트로 자료형을 바꿔 각 자릿수를 비교하면 훨씬 쉽게 구현 가능하다. 이 문제를 풀 때는 파이썬의 자료형 변경이 쉽다는 것을 몰라 함수를 통해 회문을 만들고 값을 비교해서 판별했다. 

2중 반복문으로 100부터 시작해서 1씩 키워가면서 두 수를 곱하고 회문인지 판별하면 되지만, 999부터 시작해서 1씩 내려가는 방법으로 조금 더 빠르게 답을 구할 수 있을 것이다.