Euler Solution 66
From ProgSoc Wiki
Consider quadratic Diophantine equations of the form:
x^(2) – Dy^(2) = 1
Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.
Python by Althalus
This was an interesting one. The brute force approach was looking to take months, so I did some research, piecing together bits from various wikipedia pages (Continued Fractions, Pell's Equation, and Fundamental Recurance Formulas)
from math import floor def test_eq(x,y,D): if (x**2) == 1+(D*(y**2)): return True return False def pell(D): m = [0,] d = [1,] a = [floor(D**0.5),] A = [a,] B = [1,] for n in xrange(0,10000): if test_eq(A[n],B[n], D): return A[n],B[n],D m.append(int( (d[n]*a[n]) - m[n] )) d.append(int( (D - (m[n+1])**2)/d[n] )) a.append(int( floor((a+m[n+1])/d[n+1]) )) if n == 0: A.append(int( a*a + 1 )) B.append( a ) else: A.append(int( a[n+1]*A[n] + 1*A[n-1] )) B.append(int( a[n+1]*B[n] + 1*B[n-1] )) answer = (0,0) for x in range(1,1001): if x**0.5 != int(x**0.5): res = pell(x) if res > answer: answer = res print answer