프로젝트 오일러 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$인 것들만 카운트하면 답을 구해낼 수 있다.