Project Euler/66

Problem Statement

Solving Diophantine equations of the form:

$ x^2 - D y^2 = 1 $

Link: https://projecteuler.net/problem=66

Solution Technique

Solving Diophantine equations requires the use of the continued fractions work we did in Problems 64 and 65.

Code

Core algorithm of Problem 66 solution:

public class Problem066 {
	public static void main(String[] args) { 
		solve();
	}

	public static void solve() { 
		final int DMAX = 1000;
		BigInteger x = BigInteger.ZERO;

		// Values of solution x and D at maximum
		BigInteger xmax = BigInteger.ZERO;
		int Dmax = 0;

		for(int D=1; D<=DMAX; D++) { 
			x = ContinuedFractionBig.solvePell(D);
			if(x.compareTo(xmax)>0) { 
				xmax = x;
				Dmax = D;
			}
			System.out.println("D = "+D+", x = "+x);
		}
		System.out.println(Dmax);
	}
}

This uses the ContinuedFractionBig class we already saw in Project Euler/64.

Link: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/066

ContinuedFractionBig class: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/066/ContinuedFractionBig.java

Problem066 class: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round2_050-070/066/Problem066.java