프로젝트 오일러 135번

Given the positive integers \(x,\; y\), and \(z\), are consecutive terms of an arithmetic progression, the least value of the positive integers \(n\), for which the equation, \(x^2 - y^2 - z^2 =n\), has exactly two solutions is \(n=27\):\[34^2-27^2-20^2=12^2-9^2-6^2=27\] It turns out that \(n=1155\) is the least value which has exactly ten solutions.

How many values of \(n\) less than one million have exactly ten distinct solutions?

---

자연수 \(x, \; y, \;z\) 가 등차수열을 이룰 때, 방정식 \(x^2 - y^2 - z^2 = n\) 이 \(2\) 개의 해를 갖기 위한 최소의 자연수 \(n\) 은 \(27\) 이다. \[34^2-27^2-20^2=12^2-9^2-6^2=27\] 또한 \(n=1155\) 은 방정식이 \(10\)개의 해를 갖기 위한 자연수 \(n\)의 최솟값이다.

\(n<10^6\) 에서 위 방정식이 \(10\) 개의 해를 갖는 \(n\) 은 몇 개 있을까?

'등차수열을 이루는 세 수' 라는 문구가 문제가 등장하면 세 수를 \(a-d, \; a, \; a+d\)  (단, \(a, \;d\) 는 정수 \(a>d\))로 두고 문제를 풀라는 얘기를 고등학교 수학 시간에 귀에 못이 박히게 들었을 것이다. 여기서도 예외는 없다.

     \((a+d)^2 - a^2 - (a-d)^2 = n\)

     \(4ad - a^2 =n\)

     \(a(4d-a)=n\)

이때 \(d\) 가 정수이므로 \(4d-a=b\) 라고 하면 \(d= \dfrac{a+b}{4}\) 에서 \(a+b\) 는 \(4\) 의 배수가 되어야 한다. 또한 \(a-d=a-\dfrac{a+b}{4}>0\) 이어야 하므로 \(3a>b\) 이어야 한다.

이 두 가지 조건을 만족시키는 \(a, \;b\) 의 순서쌍을 찾으면 된다.

파이썬을 이용한 코드를 보면 다음과 같다. 

 

result = [0] * (10 ** 6)

for a in range(1, 10 ** 6):
    b = 4 - (a % 4)
    while a * b < 10 ** 6:
        if 3 * a > b:
            result[a * b] += 1
        b += 4

print(result.count(10))

먼저 길이가 \(100000 +1\) 인 리스트 result를 만들어 모든 성분을 \(0\) 으로 한다. \(a\) 를 \(1\) 부터 \(1000000\) 까지 변화시키고, \(b\) 의 초기값을 \(a+b\) 가 \(4\) 의 배수가 되는 최소의 자연수로 결정한다. 그리고 \(b\) 는 \(4\) 씩 증가시면서 계속 \(a+b\) 가 \(4\) 의 배수가 되도록 한다. \(b\) 는 \(ab <10^6\) 범위에서만 생각하면 된다. 이런 중에 \(3a>b\) 인 조건을 만족시킨다면 result[ab] 요소를 \(1\) 씩 증가시킨다. 

마지막에 result 의 요소 중 그 값이 \(10\)인 것들만 카운트하면 답을 구해낼 수 있다.