## Project Euler – Problem 66

Problem 66:
Consider quadratic Diophantine equations of the form:

x^2 – D*y^2 = 1

For example, when D=13, the minimal solution in x is 649^2 – 13*180^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<=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.

``` package runner; import java.math.BigInteger; class runner { //int[] = a, b, k private static BigInteger[] chakravala(BigInteger N){ BigInteger[] arr = new BigInteger[3]; BigInteger curA; BigInteger nextA= new BigInteger(""+Integer.MAX_VALUE); BigInteger nI = BigInteger.ONE; while(true){ curA = nextA; nextA = nI.pow(2).subtract(N).abs(); if(nextA.compareTo(curA) > 0){ break; } nI = nI.add(BigInteger.ONE); } //System.out.println(nI-1); nI = nI.subtract(BigInteger.ONE); arr[0] = nI; arr[1] = BigInteger.ONE; arr[2] = nI.pow(2).subtract(N); chakravala_aux(arr, N); return arr; } //int[] = a, b, k private static void chakravala_aux(BigInteger[] arr, BigInteger N){ if(arr[2].compareTo(BigInteger.ONE) == 0) return; BigInteger a=arr[0], b=arr[1], k=arr[2], kabs = k.abs(); //Calculate m s.t. |m*m-N| is minimal BigInteger mNext = findMin(a,b,kabs); BigInteger curA, nextA= new BigInteger(""+Integer.MAX_VALUE); while(true){ curA = nextA; nextA = mNext.pow(2).subtract(N).abs(); if(nextA.compareTo(curA) > 0){ break; } mNext = mNext.add(kabs); } BigInteger m = mNext.subtract(kabs); //System.out.println(m); arr[0] = (a.multiply(m).add(N.multiply(b))).divide(kabs);//(a*m+N*b)/kabs; arr[1] = (a.add(b.multiply(m))).divide(kabs);//(a+b*m)/kabs; arr[2] = m.pow(2).subtract(N).divide(k);//(m*m - N)/k; chakravala_aux(arr, N); } private static BigInteger findMin(BigInteger a, BigInteger b, BigInteger k){ for(BigInteger i = BigInteger.ZERO; i.compareTo(k)< 0; i=i.add(BigInteger.ONE)){ if(a.add(b.multiply(i)).mod(k).compareTo(BigInteger.ZERO) == 0) return i; } return BigInteger.ZERO; } public static void main (String[] args) throws java.lang.Exception { long time = System.currentTimeMillis(); BigInteger max = BigInteger.ZERO; int maxd = 0; for(int d=2;d<=1000;d++){ if(Math.sqrt(d) == Math.floor(Math.sqrt(d))) continue; BigInteger[] t = chakravala(new BigInteger(""+d)); if(t[0].compareTo(max) > 0){ max = t[0]; maxd = d; } } System.out.println("d:"+maxd); System.out.println("time:"+(System.currentTimeMillis()-time)); } } ```

Notes: Pell’s equation