Euler Solution 66

From ProgSoc Wiki

Jump to: navigation, search

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.

Solutions

Python by Althalus

Runtime: 0.154

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[0],]
    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[0]+m[n+1])/d[n+1]) ))

        if n == 0:
            A.append(int( a[0]*a[1] + 1 ))
            B.append( a[1] )
        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[0] > answer[0]:
            answer = res 
print answer
Personal tools