Project Euler 66 - Diophantine Equation

Official link: https://projecteuler.net/problem=66

I am not happy with my Solution as I do not fully understand why my algorithm works, it uses an altered algorithm of Problem 64

Thought Process

This problem is asking for the minimum x such that (x,y) is a solution to the Pells Equation x^2 - Dy^2 = 1, and luckily on the same page we can find a way to solve the equation using continued fractions, see Problem 64 for an explanation on this.

The following theorem is stated in the above linked pages

We can start with h(1) = a(0) because we know that we are not dealing with any cases where sqrt(N) is a perfect square.

Then for each D that is not a perfect square, we find the first solution using h(n) and k(n) and add [x, D] to a list, which we can then sort

Interactive Code

Enter an integer (yourinput)

Code will output [x, D] where x is the largest x such that x^2 - Dy^2 = 1 is minimal for all D <= yourinput

Page updated

Google Sites

Report abuse