프로젝트 오일러 136번

The positive integers, \(x, \;y,\) and \(z\), are consecutive terms of an arithmetic progression. Given that \(n\) is a positive integer, the equation, \(x^2 - y^2 - z^2 =n\), has exactly one solution when \(n=20\):\[13^2-10^2-7^2=20\] In fact there are twenty-five values of \(n\) below one hundred for which the equation has a unique solution.

How many values of \(n\) less than fifty million have exactly one solution?

---

자연수 \(x, \;y,\; z\) 가 이 순서대로 등차수열을 이룬다고 한다. \(n=20\) 일 때, 방정식 \(x^2 - y^2 - z^2 = n\) 은 다음과 같이 정확히 하나의 해를 갖는다. \[13^2-10^2-7^2=20\] \(n <100\) 인 범위에서 위 방정식이 정확히 하나의 해를 갖게 하는 \(n\) 의 값은 \(25\) 개 존재한다. \(n < 5 \times 10 ^7\) 범위에서 위 방정식의 해가 \(1\) 개만 존재하게 하는 \(n\) 은 몇 개나 있을까?

이 문제를 처음엔 단순하게 생각하여 135번의 풀이를 그대로 이용하면 쉽게 해결될 수 있을 것으로 판단했다. 실제로 135번의 풀이를 이용하여 답을 얻을 수는 있었지만 답을 얻어 내기 위해 무려 2분 이상을 기다려야 했다. 그래서 뭔가 다른 방법을 생각해 봤지만, 여간해서는 시간을 줄이기 힘들었다. 그래서 구글링을 통해 mathblog 의 풀이법을 보게 되었고, 여기서는 mathblog 의 내용을 소개하려고 한다.  

먼저 \(n= 2^r \times s\) 의 형태로 표현하도록 하자. 이렇게 되면 \(s\) 는 홀수가 될 것이다. 또한 135번 에서처럼 등차 수열을 이루는 세 수를 \(a+d,\; a, \; a-d\) 로 나타낼 것이고 결국 \(a(4d-a)=n\) 이 될 것이다. 

(1) \(r=0\) 이고 \(s\) 는 소수인 경우 (\(s\) 는 홀수 이어야 하므로 \(2\) 는 제외)

이 경우 \(a=n,\; (4d-a)=1\) 이거나 \(a=1, \; (4d-a)=n\) 이 된다. 두 경우 모두 \(d=\dfrac{n+1}{4}\) 이고 \(d\) 가 자연수 이어야 하므로 \(n=4k+3\) (단, \(k\) 는 음이 아닌 정수) 가 된다. 

이때, \(a-d\) 는 각각 \(a-d= \dfrac{3n-1}{4},\; a-d=\dfrac{3-n}{4}\) 가 되는데, 후자의 경우 \(a-d \le 0\) 이 되므로 해가 존재하지 않는다. 

따라서 \(a=n, \; (4d-a) =1\) 일 때, \(x= \dfrac{5n+1}{4}, \; y=n, \; z=\dfrac{3n-1}{4}\) 의 단 하나의 해가 존재한다.  

결국 \(n\) 이 \(4k+3\) (단, \(k\) 는 음이 아닌 정수) 꼴의 소수이면 해가 단 하나 존재한다는 것을 알 수 있다. 

(2) \(r=0\) 이고 \(s\) 는 소수가 아닌 홀수인 경우 

이 경우 \(s=p \times q\) (단, \(p, \;q\) 는 모두 홀수) 은 음이 아닌 정수) 로 표현할 수 있다. 따라서 여기서는 다음의 세 가지 경우로 생각할 수 있다.

① \(a=pq,\; (4d-a)=1\) 인 경우

이 경우 \(d=\dfrac{pq+1}{4}\) 이고 \(d\) 는 자연수이어야 하므로 \(p,\;q\) 중 하나는 \(4k+1\) 나머지 하나는 \(4l+3\) 의 꼴이 되어야 한다. (단, \(k, \; l\) 은 음이 아닌 정수)

이 때, \(a-d=pq-\dfrac{pq+1}{4}=\dfrac{3pq-1}{4}\) 가 되고 \(a-d>0\) 이어야 한다. 이런 조건을 만족하는 \(p, \;q\) 의 순서쌍은 여러 개 존재할 수 있으므로 우리가 찾는 경우가 아니다.

② \(a=p, \; (4d-a)=q\) 인 경우

이 경우 \(d=\dfrac{p+q}{4}\) 가 되고 \(d\) 는 자연수이어야 하므로 \(p, \;q \) 중 하나는 \(4k+1\) 나머지 하나는 \(4l+3\) 의 꼴이 되어야 한다. (\(\because p,\;q\) 는 모두 홀수)

이때, \(a-d=p-\dfrac{p+q}{4}=\dfrac{3p-q}{4}\) 가 되고, \(a-d>0\) 이어야 한다. 이런 조건을 만족하는 \(p, \;q\) 의 순서쌍은 여러 개 존재할 수 있으므로 우리가 찾는 경우가 아니다.

③ \(a=1, \; (4d-a)=pq\) 인 경우

이 경우 \(d= \dfrac{pq+1}{4}\) 이고, \(d\) 는 자연수이어야 하므로 \(p,\;q\) 중 하나는 \(4k+1\) 나머지 하나는 \(4l+3\) 의 꼴이 되어야 한다. (단, \(k, \; l\) 은 음이 아닌 정수)

이때, \(a-d=1-\dfrac{pq+1}{4} = \dfrac{3-pq}{4}\) 이고 \(a-d>0\) 이어야 한다. 그런데 이 경우엔 \(a-d \le 0\) 이 되므로 조건을 만족하지 않는다. 결국 이 경우는 해가 없다. 

위에서 볼 수 있듯이 이 경우에는 해가 여러 개 존재하거나 혹은 해가 없는 경우 뿐이다. 

(3) \(r=1\) 이고 \(s\) 가 홀수인 경우

이 경우는 \(a\) 와 \((4d-a\) 가 하나는 짝수, 하나는 홀수가 되어야 한다. 이때, \(d={홀수}{4}\) 꼴이 되어 절대로 \(d\) 가 자연수가 될 수 없으므로 우리가 찾는 경우가 아니다.

즉, 해가 존재하지 않는다. 

(4) \(r=2\) 이고 \(s\) 가 소수인 경우 (\(s\) 는 홀수 이므로 \(2\) 는 제외)

이때 \(s \le \dfrac{5 \times 10^7}{4}\) 가 되고, 다음의 다섯 가지 경우를 생각해 볼 수 있다.

① \(a=1,\; (4d-a)=4s\) 인 경우

이 경우 \(d=\dfrac{홀수}{4}\) 가 되어 \(d\) 가 자연수가 될 수 없다.

② \(a=2,\; (4d-a)=2s\) 인 경우

이 경우 \(d=\dfrac{2s+2}{4}\) 가 되어 \(d\) 는 항상 자연수가 된다. 또한 \(a-d=2-\dfrac{2s+2}{4}=\dfrac{6-2s}{4}\) 이고 \(a-d>0\) 이어야 하는데, \(a-d \le 0\) 이므로 해가 존재하지 않는다.

 

③ \(a=2s,\; (4d-a)=2\) 인 경우

이 경우 \(d=\dfrac{2s+2}{4}\) 가 되어 \(d\) 는 항상 자연수가 된다. 또한 \(a-d=2s-\dfrac{2s+2}{4} =\dfrac{6s-2}{4}\) 이고 \(a-d>0\) 이므로 이 경우 \(x=\dfrac{10s+2}{4},\; y=2s, \; z=\dfrac{6s-2}{4}\) 의 하나의 해를 갖게 된다. 

따라서 \(n=4s\) 이면 단 하나의 해를 갖게 된다. 

④ \(a=4, \; (4d-a)=s\) 인 경우

이 경우 \(d=\dfrac{홀수}{4}\) 이므로 \(d\) 가 자연수가 될 수 없고, 따라서 해가 존재하지 않는다.

⑤ \(a=4s, \; (4d-a)=1\) 인 경우

이 겨우 \(d=\dfrac{홀수}{4}\) 이므로 \(d\) 가 자연수가 될 수 없고, 따라서 해가 존재하지 않는다.

⑥ \(a=s, \; (4d-a)=4\) 인 경우 

이 경우 \(d=\dfrac{홀수}{4}\) 이므로 \(d\) 가 자연수가 될 수 없고, 따라서 해가 존재하지 않는다.

위에서 볼 수 있듯이 \(n=4s\) (단, \(s \le \dfrac{5 \times 10^7}{4}\) 인 2가 아닌 소수) 의 꼴이면 단 하나의 해를 갖게 된다. 

(5) \(r=2\) 이고 \(s\) 는 소수 아닌 홀수 인 경우

(4)의 경우와 마찬가지로 생각하면 되지만 우리가 고려해야 하는 경우는 ③의 경우다. 나머지 경우는 (2) 경우와 마찬가지로 여러 개의 해를 갖거나 혹은 해를 갖지 않는다. 따라서 이 경우도 ③의 경우만 고려하면 된다.

\(a=2s, \; (4d-a)=2\) 인 경우 \(d=\dfrac{2s+2}{4}\) 가 되어 \(d\) 는 항상 자연수가 된다. 또한 \(a-d=\dfrac{6s-2}{4}\) 이기 때문에 \(s=1\) 인 경우만 \(a-d>0\) 이고 이 때 \(x= 3, \; y=2,\; z=1\) 의 해 하나만을 갖는다. 

따라서 \(n=4\) 이면 단 하나의 해를 갖는다.

(6) \(r=3\) 이고 \(s\) 는 홀수인 경우 

이 경우에는 \((a, \; 4d-a)\) 의 순서쌍이 \((1, \; 8s),\; (8s, \;1)\), \((2, \;4s),\; (4s, \;2)\), \((4, \;2s),\; (2s, \;4)\), \((8,\;s),\;(s,\;8)\) 의 경우가 가능하다. 어떤 경우라도 \(d\) 가 자연수가 될 수 없기 때문에  해는 존재하지 않는다.

(7) \(r=4\) 이고 \(s\) 가 소수인 경우 (\(s\) 는 홀수 이므로 \(2\)는 제외)

이 경우는 \(s \le \dfrac{5 \times 10^7}{16}\) 이고 \((a, \; 4d-a)\) 의 순서쌍이 \((1, \; 16s),\; (16s, \;1)\), \((2, \;8s),\; (8s, \;2)\), \((4, \;4s),\; (4s, \;4)\), \((8,\;2s),\;(2s,\;8)\), \((16, \;s),\;(s, \;16)\) 의 \(10\) 가지 경우가 가능하다. 이때 \((4,\; 4s),\;(4s, \;4)\) 를 제외한 나머지는 \(d\) 가 자연수가 될 수 없으므로 해가 존재하지 않는다.

 

① \(a=4, \; (4d-a)=4s\) 인 경우

이 경우 \(d=s+1\) 이 되어 자연수가 되는데, \(a-d=3-s\)가 되어 \(a-d<=0\) 이 된다. 따라서 해가 존재하지 않는다.

② \(a=4s, \; (4d-a)=4\) 인 경우

이 경우 \(d=s+1\)이 되어 자연수가 되고, \(a-d=3s-1\) 이 되어 \(a-d>0\) 을 만족한다. 따라서 \(x= 5s+1,\; y=4s,\; z= 3s-1\) 의 해 하나만을 갖게 된다. 

위에서 볼 수 있듯이 \(n=16s\) (단, \(s \le \dfrac{5 \times 10^7}{16}\) 인 \(2\) 가 아닌 소수) 이면 단 하나의 해를 갖는다. 

(8) \(r=4\) 이고 \(s\) 가 소수가 아닌 홀수인 경우

(7)의 경우와 마찬가지로 \(10\) 가지 경우로 나눌 수 있지만, 이 중 우리가 고려해야 하는 경우는 \(a=4, \; (4d-a)=4s\) 인 경우 뿐이다. 나머지는 (2)의 경우와 마찬가지로 해를 갖지 않거나 여러 개의 해를 갖게 된다.

\(a=4, \; (4d-a)=4s\) 이면 \(d=s+1\) 이 되고, \(a-d=3-s\) 가 되어 \(a-d>0\) 을 만족시키는 \(s\)는 \(1\) 밖에 없다. 따라서 \(n=16\) 인 경우 하나의 해 \(x=6, \; y=4, \; z=2\) 가 존재한다. 

따라서 \(n=16\) 이면 단 하나의 해가 존재한다.

(9) \(r>4\) 이고 \(s\) 가 홀수인 경우

\((a, 4d-a)\) 의 순서쌍이 \(2^p, \; 2^{r-p}s),\; (2^{r-p}s, \; 2^p)\) (단, \(0 \le p \le r\)) 의 어떤 경우라고 하더라도, 해는 여러 개 존재하게 된다. 이 부분은 직접 한 두개 해 보시면 도움이 될 듯...

결국 해를 하나만 갖게 되는 경우는 다음의 세 가지 경우로 정리할 수 있다.

1. \(n=4p\)   (단, \(p=1\) 이거나 \(p\) 는 \(2\)가 아닌 소수)

2. \(n=16p\)   (단, \(p=1\) 이거나 \(p\) 는 \(2\)가 아닌 소수)

3. \(n=p\)   (단, \(p=4k+3\) 꼴의 소수, \(k\) 는 음이 아닌 정수)

따라서 일단 \(n=4\) 인 경우 \(n=16\) 인 경우를 카운트 하고 \(5 \times 10^7\) 미만의 \(2\) 를 제외한 소수들에 대해서 

1. \(\dfrac{5 \times 10^7}{4}\) 보다 작은 소수인 경우

2. \(\dfrac{5 \times 10^7}{16}\) 보다 작은 소수인 경우

3. \(4k+3\)  (단, \(k\) 는 음이 아닌 정수) 꼴의 소수인 경우

만을 카운트하게 되면 답을 구해낼 수 있다.