프로젝트 오일러 66번

66번 문제는 다음과 같다.

Consider quadratic Diophantine equations of the form:

x² – Dy² = 1

For example, when D=13, the minimal solution in x is 649² – 13×180² = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

3² – 2×2² = 1
2² – 3×1² = 1
9² – 5×4² = 1
5² – 6×2² = 1
8² – 7×3² = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

결국 D가 주어졌을 때, \(x^2 -Dy^2 =1\) 을 만족시키는 가장 작은 자연수 \(x\) 를 찾는 것이 해야할 일이다.

만약 D가 1부터 1000까지 변할 때 (물론 D는  완전제곱수가 아니어야 한다.) 위의 조건을 만족하는 \(x\) 들을 모두 찾는다면 가장 큰 \(x\) 값이 나오는 \(D\) 는 얼마일까? 뭐 이런걸 묻는 문제이다.

사실 이 문제는 상당히 단순하게 생각할 수 있다. \(x, \;y\) 를 1부터 증가시키면서 조건을 만족하는 자연수 \(x, \; y\) 값을 찾으면 되기 때문이다. 만약 이런 생각으로 문제를 풀다가 해결책이 없어서 여기까지 흘러 들어왔다면 분명히 \(D=61\) 일 때, \(x, \;y\) 를 찾지 못했을 가능성이 농후하다. 똑같은 과정을 필자도 겪었기 때문이다.

위에 주어진 식 \(x^2-Dy^2=1\) 은 pell's equation 이란 것이다. 이 펠 방정식의 풀이법을 정확히 아는 것은 상당한 수학적 지식을 요구할 뿐만 아니라 프로그래밍 공부를 하는 목적에 어울리지 않기 때문에 (이렇게 생각해야만 프로그래밍 공부를 계속할 수 있지 않을까? 수학적인 부분때문에 프로그래밍을 포기할 수 없으므로) 여기서는 간단하게 펠 방정식 풀이의 접근 방법을 소개하고자 한다.

주어진 방정식을 다음과 같이 변형해 보자.

\[ \sqrt{D}=\dfrac{\sqrt{x^2-1}}{y} \approx \dfrac{x}{y}\]

위 식을 만족하는 자연수 \(x, \;y\) 는 결국 \(\sqrt{D}\) 의 근삿값을 나타내는 유리수의 분자와 분모가 된다고 생각할 수 있다. 이 근삿값은 이미 64번에서 봤던 방법으로 연분수 전개(continued fraction expansion) 로 부터 구할 수 있다.

예를 들어,

\[\begin{split} \sqrt{7} &= 2+\sqrt{7}-2 =2+\dfrac{1}{\dfrac{1}{\sqrt{7}-2}}=2+\dfrac{1}{\dfrac{\sqrt{7}+2}{3}} \\ &= 2+\dfrac{1}{1+\dfrac{\sqrt{7}-1}{3}}=2+\dfrac{1}{1+\dfrac{1}{\dfrac{\sqrt{7}+1}{2}}} \\ &=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{\sqrt{7}-1}{2}}} =2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{\dfrac{\sqrt{7}+1}{3}}}} \\ &= 2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{\sqrt{7}-2}{3}}}} = \cdots \end{split}\]

이 되므로, 이를 단계단계 계산하여 \(\sqrt{7}\) 의 근삿값을 찾아내면

\(\sqrt{7}=2\)

\(\sqrt{7}=2+\dfrac{1}{1}=3\)

\(\sqrt{7}=2+\dfrac{1}{1+\dfrac{1}{1}}=\dfrac{5}{2}\)

\(\sqrt{7}=2+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1}}}=\dfrac{8}{3}\)

      \(\vdots\)

이렇게 구한 근삿값들을 나열해 보면

\[ \dfrac{2}{1}, \; \dfrac{3}{1}, \; \dfrac{5}{2}, \; \dfrac{8}{3}, \; \dfrac{37}{14}, \cdots\]

가 된다. 이 근삿값들을 이용하여 펠 방정식의 해를 찾으면

\[2^2 - 7\cdot 1^2=-3\]

\[3^2-7 \cdot 1^2 =2\]

\[5^2 - 7 \cdot 2^2 = -3\]

\[8^2 - 7 \cdot 3^2 =1\]

따라서 \(x=8, \; y=3\) 이 되는 것을 알 수 있다.

프로그래밍을 할 때, 일단 \(\sqrt{D}\) 의 근삿값을 연분수 전개로 찾아낸 다음, 분자와 분모를 각각 \(x, \; y\) 에 대입하다가 등식을 만족하는 \(x, \; y\) 를 찾아내면 된다. 이 방법으로 하게 되면 매우 빠른 시간 안에 문제를 해결 할 수 있다.

참고로  \(D=661\) 일 때, \(x=16421658242965910275055840472270471049\) 의 최댓값을 갖게 된다. 따라서 66번의 정답은 \(661\) 이다.