책 이야기

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개를 찾을 수 있어 실행시간은 여전히 필요했다.

"_"가 숫자 한 자리이며, 제곱값이 1_2_3_4_5_6_7_8_9_0인 양의 정수를 구하시오.

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

난이도 5%인 문제여서 그런지 그나마 단순한 방법으로 해결가능했다.

일단 19자리 숫자이면서 1의 자리에 0, 백 자리에 9, 만 자리에 8, 백만 자리에 7, 억 자리에 6, 백억 자리에5, 조 자리에 4, 백조 자리에 3, 경 자리에 2, 백경 자리에 1이 들어가는 숫자를 구하면 되는데,  첫 자리가 1로 시작하므로 제곱하여 백경이 되는 1,000,000,000부터 시작할 것이고, 첫 자리가 2보다 작아야 하므로 √2*1,000,000,000 보다는 작아야 할 것이다.

그리고, 1의 자리가 0이므로 마지막 숫자는 0이 되므로 이 사이의 숫자를 반복문을 통해 계산해서 어렵지 않게 구할 수 있었다.

양의 정수 x, y, z가 등차수열의 연속된 요소일 때, x2-y2-z2=n으로 구해지는 가장 작은 양의 정수 n은 n=27일 때 정확하게 2개의 해답이 있다:

342-272-202=122-92-62=27.

정확하게 10개의 해답이 있는 최소값은 n=1155일 때이다.

10개의 해답이 있는 1백만 이하의 n은 몇 개 인가?

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

등차수열이기 때문에 처음에는 x를 기준으로, x2-(x-a)2-(x-2a)2=n으로 수식을 만들어서, 정리하니 x2-6ax+5a2=-n이어서, (x-a)(x-6a)=-n이 되었다. 모양은 좀 이상했지만 처음 값 x와, 차이 a 기준으로 n의 약수의 곱이 된다는 것을 알 수 있었다.

(제대로 접근한 사람은 가운데 y를 기준으로 (y+a)2-y2-(y-a)2=n으로 수식을 만들어서, 전개하면 4ay-y2=n이 되고, 차이 a 기준으로 정리하면 a=(n+y2)/4y가 된다)

처음에는 약수의 갯수만 관련이 있다고 생각하고 약수가 20개 인 수(두 수의 곱이므로 절반인 10개의 해답을 만드는 수로 추정)의 갯수를 찾도록 구현했는데, 약수 만드는 함수의 성능이 나빠서 시간이 너무 많이 걸리고, 이를 개선해서 조금 빨리 돌아가도록 했는데 오답이 나왔다.

다시 확인해보니, 후보가 되는 것은 약수가 맞지만 두 약수의 곱이 아니기 때문에 약수를 대상으로 등차수열 조건(a=(n+y2)/4y, a<y, a는 정수)을 만족하는지 확인해야 되는 것이었다. 그렇게, 단순히 약수의 갯수를 세는 것이 아니라 약수를 대상으로 등차수열을 만들 수 있는 것이 몇 개인지 확인하도록 변경해서 답을 구할 수 있었다.

그리고, 처음에는 n의 약수를 1~n/2까지 비교하도록 되어 있던 함수 성능을 개선한 이후에야 수분 내에 답을 구할 수 있어서, 성능의 중요성을 다시 한 번 느꼈다.

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

숫자 체인은 각 자릿수를 더하여 새로운 숫자를 구하는 것을 끝날때까지 반복하면서 생성된다.

예를 들면 다음과 같다.

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

따라서, 어떤 체인이든 1 또는 89가 되면 무한반복되면서 정체된다. 가장 놀라운 것은 모든 숫자는 결국 1 또는 89에 이른다는 것이다.

1천만 이하의 숫자 중에 89가 되는 숫자는 몇 개인가?

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

10자리수 이상은 자릿수별로 쪼개어서 제곱하고 더하는 과정을 반복하면서 89가 나오는 경우의 수를 더하도록 하면 되는 문제이다. 다만, 1천만 까지 계산하기를 요구했기 때문에 시간은 생각보다 엄청 많이 필요하게 된다.

그래도, 이 방법이 가장 정확한 방법이라 생각하고 속도를 조금 개선해보기 위해 제곱수를 매번 계산하지 않고 리스트를 만들어서 참조하게 했다. 그렇게 해서 256초가 245초로 조금 개선될 수 있었다.

문제를 해결한 후에, 인터넷을 검색해보니 동일한 순열(4666777과 6466777, 7664776)에 대해서는 한 번 계산한 결과를 이용하여 모든 체인을 계산하지 않도록 성능 개선이 가능하다고 되어 있다. 정말 세상은 넓고 해결방안은 다양하다는 것을 새삼 느끼게 된다.

The sum of the squares of the first ten natural numbers is,

1²+2²+...+10²=385

The square of the sum of the first ten natural numbers is,

(1+2+...+10)²=55²=3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025−385=2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

처음 10개 자연수 제곱의 합계는 1²+2²+...+10²=385이다.

처음 10개 자연수 합계의 제곱은 (1+2+...+10)²=55²=3025이다.

즉, 처음 10개 자연수 합계의 제곱과 제곱의 합계의 차이는 3025-385=2640이다.

처음 100개 자연수 합계의 제곱과 제곱의 합계의 차이를 구하시오.

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

다른 언어로 작성했으면 합계의 제곱 숫자가 커서 정수(integer) 범위를 넘어서는 에러가 생기고 문제 해결이 복잡해지는 경우가 발생할 수도 있겠지만, 파이썬에서는 그리 큰 문제 없이 제곱의 합계, 합계의 제곱을 구하고 차이를 구할 수 있다.