[E066] 펠방정식의 최소해

프로젝트 오일러 66번

아마 100번 이하대 문제에서 가장 어려운 문제일 수도 있겠다는 생각이 들었는데, 의외로 이 앞의 두 문제를 차근히 풀었다면 손쉽게 풀릴 수 있는 문제이다. (띄엄띄엄 풀려다보니 거의 보름을 고민했다.) 정수해를 갖는 다항 방정식을 디오판토스 방정식이라고 하는데, 펠의 방정식은 이 중에서 쌍곡선의 방정식처럼 생긴 것으로 아래와 같이 생겼다.

$$x^2 -D\cdot y^2 = 1 , n \in \mathbb{Z}^{+} $$

펠의 방정식은 디오판토스 방정식의 특별한 한 형태로 양의 제곱수가 아닌 정수 D에 대해서 위 식을 만족하는 양의정수 x, y의 쌍을 찾는 문제이다. 이 순서쌍은 일종의 패턴을 가지는데,

$$ \begin{align} x_{k+1} & = x_{1}x_{k} + ny_{1}y_{k} \\
y_{k+1} & =x_{1}y_{k} + y_{1}x_{k} \end{align} $$

즉 x, y의 최소해를 알면 점화식을 통해서 그 이후의 값을 찾을 수 있다. 그 최소해는? brute force로 찾을까?

아쉽게도 이 문제의 정답에 해당하는 D에 대한 최소해 중 x의 값은 무려 16421658242965910275055840472270471049에 달하기 때문에 그냥 루프 돌려서 풀려면 그만한 전기세를 내기 위한 막대한 자금이 필요하다.

펠 방정식의 해는 \( \frac{x}{y} = \sqrt{D} \)이 되는 유리 근사값이며, 이는 D의 제곱근을 연분수 전개한 값 중에서 찾을 수 있게 된다.

따라서 이 문제를 풀기 위해서는

  1. \(\sqrt{D}\)를 연분수로 표현하는 법을 알아야 하고
  2. 연분수 표현을 전개하여 이를 각 단계별로 유리수 꼴(분자와 분모)로 구할 필요가 있다.

그리고 위 각 조건들은 E064, E065의 해법이다. 즉 앞선 문제를 열심히 풀었다면 그리 어렵지 않게 풀어낼 수도 있다.

당연히, 그냥 더하거나 나누는 것은 부동소수점 연산의 부정확성 때문에 망하는 지름길이 되므로, 분수를 효율적으로 표현하기 위한 데이터형을 정의할 필요가 있으며, 만약 사용하는 프로그래밍 언어가 큰 수를 지원하지 않는다면, 이에 대한 대비책도 있어야 한다.

그야말로 지금까지의 문제를 풀어온 곳에서 사용한 많은 스킬을 집약적으로 사용하는 문제이다.