Pell Equation

C++. This is the Problem 66 from Project Euler.

Question: 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:

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 ≤ 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. Link to the page.

Solution: We could call it “Pell Equation” as well. To be honest, it was pretty exhaustive to write an efficient algorithm for its solution.  It was harder than I thought. I implemented “Chakravala Method”. Main problem was rounding error  in C++ when the numbers getting really high (particularly after 16 digit). That’s why, I decided to use double data types for x, and y. Algorithm starts with setting up m value for a [x,y,k] trivial triple, then goes up to search x, y, and k values. When k reaches 1, that gives x and y values, and stops there. Also, there is a shortcut calculation for k = -1 and abs(k) = 2 values inside the algorithm. The answer is 661.