Consider quadratic Diophantine equations of the form:
x2 – Dy2 = 1
For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 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:
32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 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.
다음 형태의 디오판토스 방정식을 생각해 보자:
x2 – Dy2 = 1
예를 들어, D=13일 때, x가 최소가 되는 답안은 6492 – 13×1802 = 1이다..
D가 제곱수일 때 양의 정수에서 답안이 없다는 것은 예상 가능하다.
D={2, 3, 5, 6, 7}일 때 x의 최소 답안을 찾으면 다음과 같다:
32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 1
즉, D가 7보다 작거나 같은 경우 x의 최소값 답안에서, 가장 큰 x 값은 D=5일 때 구해진다.
D ≤ 1000일 때 x의 최소값 답안에서 가장 큰 x 값을 구하시오.
--------------------------------------------------------------------------
위키피디아에서는 디오판토스 방정식(Diophantine equation)을 2개 이상의 미지수와 정수 계수가 있는 다항식으로 설명하고 있다. 디오판토스 방정식 자체는 일반적인 방정식을 이야기하는데, 이 문제에서는 좀 더 특수한 경우를 설명하고 있고, 이것을 펠 방정식(Pell's equation)이라 부른다고 한다.
처음에는 x=(1+Dy2)**0.5를 이용해 계산했으나 실수부분 오차로 오답을 계산해내서, 정확한 계산을 위해 x2과 1+Dy2을 바로 비교했고, y를 1부터 시작하지 않고 x/√d 부터 시작하게 해서 계산 시간을 줄였다. 그렇게 해도 x가 17억 이상이 되는 d=61인 경우에는 시간이 6000초 이상 걸리는 등 많은 시간이 필요했지만, 이전보다는 좀 더 빠르게 동작했다.
그래도, 시간이 너무 많이 걸려서 검색해 보니 정답을 구하기 위해서는 x값을 16x1036 넘게 계산해야 된다고 한다. 위키피디아 문서를 보면 펠 방정식에 해결을 위한 4가지 방법(연분수(fundamental solution via continued fractions), 연분수에서 나온 추가 방법(additional solutions from fundamental solution), 빠른 알고리즘(concise representation and faster algorithms), 퀀텀 알고리즘(quantum algorithm))을 제시하고 있는데, 이 방법을 적용하지 않고 통상적인 방법으로는 답을 구할 수 없는 것을 확인하고, 연분수의 이해를 돕는 64번, 65번 문제를 해결한 이후에 다시 풀어보았다.
문제를 D를 기준으로 다시 보면 √D=√(x2-1)/y가 되고, 이는 연분수의 형태와 비슷하게 된다. 그래서, D를 기준으로 1000까지 반복하면서 연분수로 나오는 숫자(x, y)를 대입해서 공식(x2-Dy2=1)을 충족하는 경우를 찾았더니 몇 시간을 기다려도 답을 구하지 못하던 것을 0.5초도 되지 않아 구할 수 있었다.
다만, 연분수 계산을 위해 2번째 이전 x, y값을 알고 있어야 되어서 프로그램이 길어지게 되었는데, 파이썬 특성을 잘 살리면 좀 더 간결하게 프로그래밍 가능했을 것 같다.
