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

Post a comment | Trackback URI