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