(3 votes, average: 5.00 out of 5)

## Project Euler Problem 66 Solution

#### Problem Description

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.

#### Analysis

Using the chakravala method for solving minimal solutions to Pell’s Equation

#### Solution

Runs < 1 second in Python.

```from Euler import sqrt, prime_sieve   def pell(d): p, k, x1, y, sd = 1, 1, 1, 0, sqrt(d)   while k != 1 or y == 0: p = k * (p/k+1) - p p = p - int((p - sd)/k) * k   x = (p*x1 + d*y) / abs(k) y = (p*y + x1) / abs(k) k = (p*p - d) / k   x1 = x   return x   limit = 1000 print max([(pell(d),d) for d in prime_sieve(limit)])```

D=92821 for D ≤ 100000 in 15 seconds.

## Discussion

### 2 Responses to “Project Euler Problem 66 Solution”

1. Will you please explain , how you implement these steps ??

p = k * (p/k+1) – p
p = p – int((p – sd)/k) * k

Posted by Mayank | May 29, 2013, 5:30 AM