책 이야기

양의 정수 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까지 비교하도록 되어 있던 함수 성능을 개선한 이후에야 수분 내에 답을 구할 수 있어서, 성능의 중요성을 다시 한 번 느꼈다.

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

3330씩 커지는 등차수열 1487, 4817, 8147은 2가지 면에서 특이하다. (i) 세 숫자 모두 소수이고, (ii) 각 4자리 숫자는 서로의 순열이다.

1, 2, 3자리 소수에서는 이런 특성을 가지는 등차수열이 없으며, 4자리 숫자에서 하나의 등차수열이 더 있다.

이 수열의 3개 항목을 연결한 12자리 숫자는 무엇인가?

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

첫 시행착오는 3개의 숫자가 서로의 순열일 뿐이지, 한쪽 방향으로 각 자리수를 이동하는 것이 아니었는데 그런 방식으로 해결하려 했던 것이다. 방향을 잘못 잡았던 덕분에 문제를 처음부터 다시 해결해야 했다.

해결한 방법은 지금 생각하면 효율성은 낮지만, 4자리 소수를 구하고, 그 수로 만들 수 있는 순열 중 소수인 것을 구하고, 소수+순열이 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다.

이 방법의 성능을 개선할 방법으로는 4자리 소수 리스트를 만든 후에, 특정 숫자(소수)와 그 숫자로 만들 수 있는 순열 중 소수인 것을 소수 리스트에서 삭제하면서 구하고, 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다. 이렇게 하면 중복되는 소수여부 검사, 순열 작성 등의 부담이 줄어들 것이다.