Euler Problem 66

Consider quadratic Diophantine equations of the form:

$x^2 - Dy^2 = 1$

For example, when $D=13$, the minimal solution in x is $649^2 – 13\times180^2 = 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×2^2 = 1
2^2 – 3×1^2 = 1
9^2 – 5×4^2 = 1
5^2 – 6×2^2 = 1
8^2 – 7×3^2 = 1

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

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


In [1]:
from fractions import Fraction

# Reciprocal of (a + b*sqrt(d))
def recip(a,b,d):
    D = a*a-b*b*d
    return (a/D, -b/D)

# Integer part of (a + b*sqrt(d))
def intpart(a,b,d):
    return int(a+b*d**.5)

def cfrac(d):
    if d == int(d**.5+.5)**2:
        return (0,0)
    a = Fraction(0)
    b = Fraction(1)
    term = intpart(a,b,d)
    a = a - term
    p1,q1 = 1,0
    p2,q2 = term,1
    while p2*p2-d*q2*q2 != 1:
        a,b = recip(a,b,d)
        term = intpart(a,b,d)
        p1,p2 = p2,p2*term+p1
        q1,q2 = q2,q2*term+q1
        a = a - term
    return (p2,q2)

record = 0
best_n = 0
for n in range(1001):
    c = cfrac(n)
    if c[0] > record:
        record = c[0]
        best_n = n
print(best_n)


661

In [ ]: