프로젝트 오일러 108번

In the following equation \(x, \; y,\) and \(n\) are positive integers.

\[\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}\]

For \(n=4\) there are exactly three distinct solutions:

\[\begin{split} \dfrac{1}{5} + \dfrac{1}{20} &= \dfrac{1}{4} \\ \dfrac{1}{6} + \dfrac{1}{12} &= \dfrac{1}{4} \\ \dfrac{1}{8} + \dfrac{1}{8} &= \dfrac{1}{4} \end{split}\]

What is the least value of \(n\) for which the bumber of distinct solutions exceeds one-thousand?

---

다음 방정식에서 \(x, \; y, \;n\) 은 자연수이다.

\[ \dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}\]

\(n=4\) 일 때 위 방정식은 다음과 같이 세 개의 해를 갖는다.

\[\begin{split} \dfrac{1}{5} + \dfrac{1}{20} &= \dfrac{1}{4} \\ \dfrac{1}{6} + \dfrac{1}{12} &= \dfrac{1}{4} \\ \dfrac{1}{8} + \dfrac{1}{8} &= \dfrac{1}{4} \end{split}\]

서로 다른 해의 개수가 1000개를 넘게 되는 최소의 자연수 \(n\) 은 얼마일까?

문제에서 \(x, \; y, \; n\) 은 모두 양의 정수라고 했고, \(\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}\) 을 만족하므로 \(x, \; y\) 는 모두 \(n\) 보다 큰 양의 정수입니다. 이를 정리하면 다음과 같습니다.

\[\dfrac{x+y}{xy} = \dfrac{1}{n}\]

\[n(x+y) = xy\]

\[xy-nx-ny=0\]

양변에 \(n^2\) 을 더해주면

\[xy-nx-ny+n^2 = n^2\]

\[(x-n)(y-n)=n^2\]

여기서 \(x-n\) 과 \(y-n\) 이 모두 양의 정수이므로 (\(\because x>n, \; y>n\))

\(x-n\) 과 \(y-n\) 은 모두 \(n^2\) 의 양의 약수가 된다.

따라서 이 방정식의 가질 수 있는 정수해의 개수는 \(n^2\) 의 양의 약수의 개수와 같다고 생각할 수 있다.

하지만 문제에서 예로 보여 주듯이, \(x, \; y\) 가 서로 값을 교환하는 경우를 따로 고려하지 않고 있기 때문에, 이 부분을 생각하여 답을 결정해야 한다.

이 부분을 이해하기 위해서는 양의 약수의 개수에 관한 지식이 있어야 한다. 이 부분은 "양의 약수의 개수" 게시물을 확인하면 된다.

만약 \(n\) 이 \(n= P_1^{a_1} \times P_2^{a_2} \times \cdots \times P_n^{a_n}\) 으로 소인수분해 된다고 하면, \(n^2\) 은 \(n^2 =  \left ( P_1^{a_1} \times P_2^{a_2} \times \cdots \times P_n^{a_n} \right )^2 \) 으로 소인수분해 될 것이다. 이 경우 \(n^2 \) 의 양의 약수의 개수는 \((2a_1 +1) \times (2a_2 +1) \times \cdots \times (2a_n +1)\) 이 된다. 따라서 \(n^2\) 의 양의 약수의 개수를 \(k\) 개라고 한다면 \(k\)가  홀수임을 알 수 있다. 따라서 \((x, \;y)\) 쌍에서 \((2n, \;2n)\) 을 제외한 나머지 \(k-1\)개에는 \(x\) 와 \(y\) 가 서로 값을 교환하는 쌍이 반드시 존재하므로 우리가 찾는 전체 해의 개수는 \(\dfrac{k-1}{2} +1 = \dfrac{k+1}{2}\) 개가 된다.  

따라서 이 문제는 \(n^2\) 의 양의 약수의 개수가 \(k\) 개 일 때, \(\dfrac{k+1}{2} > 1000\) 을 만족하는 가장 작은 양의 정수 \(n\) 을 찾는 문제가 된다. 결국 소인수분해를 해주는 함수를 만드는 것이 관건이 될 것이다. 한 가지 팁은 소인수분해 시 소인수들이 필요할텐데, \((2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 )^2\) 의 양의 약수의 개수가 이미 1000개를 넘어가기 때문에, 소인수분해 시 소인수들의 리스트는 17까지만 가지고 계산해도 충분하다는 것이다. 아마도 수초내로 답을 얻어낼 수 있을 것이다.