Problem 66:
\nConsider quadratic Diophantine equations of the form:<\/p>\n
It can be assumed that there are no solutions in positive integers when D is square.<\/p>\n
By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:<\/p>\n
3^2 \u2013 2*2^2 = 1\r\n2^2 \u2013 3*1^2 = 1\r\n9^2 \u2013 5*4^2 = 1\r\n5^2 \u2013 6*2^2 = 1\r\n8^2 \u2013 7*3^2 = 1<\/pre>\n<\/center><\/p>\n
Hence, by considering minimal solutions in x for D<=7, the largest x is obtained when D=5.\n\nFind the value of D<=1000 in minimal solutions of x for which the largest value of x is obtained.\n\n
<\/p>\n\r\npackage runner;\r\n\r\nimport java.math.BigInteger;\r\n\r\n\r\nclass runner\r\n{\r\n\t\/\/int[] = a, b, k\r\n\tprivate static BigInteger[] chakravala(BigInteger N){\r\n\t\tBigInteger[] arr = new BigInteger[3];\r\n\t\tBigInteger curA;\r\n\t\tBigInteger nextA= new BigInteger(\"\"+Integer.MAX_VALUE);\r\n\t\tBigInteger nI = BigInteger.ONE;\r\n\t\twhile(true){\r\n\t\t\tcurA = nextA;\r\n\t\t\tnextA = nI.pow(2).subtract(N).abs();\r\n\t\t\tif(nextA.compareTo(curA) > 0){\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t\tnI = nI.add(BigInteger.ONE);\r\n\t\t}\r\n\t\t\/\/System.out.println(nI-1);\r\n\t\tnI = nI.subtract(BigInteger.ONE);\r\n\t\tarr[0] = nI;\r\n\t\tarr[1] = BigInteger.ONE;\r\n\t\tarr[2] = nI.pow(2).subtract(N);\r\n\t\t\r\n\t\tchakravala_aux(arr, N);\r\n\t\treturn arr;\r\n\t}\r\n\t\/\/int[] = a, b, k\r\n\tprivate static void chakravala_aux(BigInteger[] arr, BigInteger N){\r\n\t\tif(arr[2].compareTo(BigInteger.ONE) == 0) return;\r\n\t\tBigInteger a=arr[0], b=arr[1], k=arr[2], kabs = k.abs();\r\n\t\t\r\n\t\t\/\/Calculate m s.t. |m*m-N| is minimal\r\n\t\tBigInteger mNext = findMin(a,b,kabs);\r\n\t\tBigInteger curA, nextA= new BigInteger(\"\"+Integer.MAX_VALUE);\r\n\t\twhile(true){\r\n\t\t\tcurA = nextA;\r\n\t\t\tnextA = mNext.pow(2).subtract(N).abs();\r\n\t\t\tif(nextA.compareTo(curA) > 0){\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t\tmNext = mNext.add(kabs);\r\n\t\t}\r\n\t\tBigInteger m = mNext.subtract(kabs);\r\n\t\t\/\/System.out.println(m);\r\n\t\tarr[0] = (a.multiply(m).add(N.multiply(b))).divide(kabs);\/\/(a*m+N*b)\/kabs;\r\n\t\tarr[1] = (a.add(b.multiply(m))).divide(kabs);\/\/(a+b*m)\/kabs;\r\n\t\tarr[2] = m.pow(2).subtract(N).divide(k);\/\/(m*m - N)\/k;\r\n\t\t\r\n\t\tchakravala_aux(arr, N);\r\n\t}\r\n\tprivate static BigInteger findMin(BigInteger a, BigInteger b, BigInteger k){\r\n\t\tfor(BigInteger i = BigInteger.ZERO; i.compareTo(k)< 0; i=i.add(BigInteger.ONE)){\r\n\t\t\tif(a.add(b.multiply(i)).mod(k).compareTo(BigInteger.ZERO) == 0) return i;\r\n\t\t}\r\n\t\treturn BigInteger.ZERO;\r\n\t}\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\t\tBigInteger max = BigInteger.ZERO;\r\n\t\tint maxd = 0;\r\n\t\tfor(int d=2;d<=1000;d++){\r\n\t\t\tif(Math.sqrt(d) == Math.floor(Math.sqrt(d))) continue;\r\n\t\t\tBigInteger[] t = chakravala(new BigInteger(\"\"+d));\r\n\t\t\tif(t[0].compareTo(max) > 0){\r\n\t\t\t\tmax = t[0];\r\n\t\t\t\tmaxd = d;\r\n\t\t\t}\r\n\t\t}\r\n\t\tSystem.out.println(\"d:\"+maxd);\r\n\t\t\r\n\t\tSystem.out.println(\"time:\"+(System.currentTimeMillis()-time));\r\n\t}\r\n}\r\n<\/pre>\n