## The challenge

In mathematics, a Diophantine equation is a polynomial equation, usually with two or more unknowns, such that only the integer solutions are sought or studied.

In this challenge we want to find all integers `x, y` (`x >= 0, y >= 0`) solutions of a diophantine equation of the form:

#### x2 – 4 * y2 = n

(where the unknowns are `x` and `y`, and `n` is a given positive number) in decreasing order of the positive xi.

If there is no solution return `[]` or `"[]"` or `""`. (See “RUN SAMPLE TESTS” for examples of returns).

#### Examples:

 ``````1 2 3 4 5 `````` ``````// [[45003, 22501], [9003, 4499], [981, 467], [309, 37]] solEquaStr(90005) // [] solEquaStr(90002) ``````

#### Hint:

x2 – 4 * y2 = (x – 2*y) * (x + 2*y)

## The solution in Kotlin

Option 1:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````package diophequa import kotlin.math.sqrt fun solEquaStr(n:Long):String { if ( (n % 2 == 0L) and (n/2 % 2 == 1L)) return "[]" val lower = if (n % 2 == 0L) {2} else {1} val limit = sqrt(n.toDouble()).toInt() val strings = mutableListOf() for (a in lower..limit step 2) { if (n % a != 0L) continue val b = n/a if (((a+b) % 2 != 0L) or ((b-a) % 4 != 0L)) continue val x = (a+b)/2 val y = (b-a)/4 strings.add(listOf(x,y).joinToString(prefix = "[",postfix = "]")) } return strings.joinToString(prefix = "[",postfix = "]") } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````package diophequa import kotlin.math.ceil import kotlin.math.pow import kotlin.math.sqrt fun solEquaStr(n: Long): String { val pairs = mutableListOf>() val (low, high) = ceil(sqrt(n.toDouble())).toLong() to ceil(n.toDouble() / 2).toLong() (high downTo low).forEach { x -> val y = findY(n, x) if (y.isInteger()) pairs.add(x to y.toLong()) } return pairs .sortedByDescending { it.first } .joinToString(", ", "[", "]") { (x, y) -> "[\$x, \$y]" } } fun findY(n: Long, x: Long) = sqrt((x.toDouble().pow(2) - n) / 4) fun Double.isInteger() = this == Math.floor(this) && !this.isInfinite() Best Practices1Clever0 0ForkLink ``````

Option 3:

 ``````1 2 3 4 5 6 7 8 9 `````` ``````package diophequa fun solEquaStr(n:Long):String { return (1..Math.sqrt(n.toDouble()).toInt()).filter { (n % it).toInt() == 0 && (n / it - it).toInt() % 4 == 0 }.map { listOf((n / it + it) / 2, (n / it - it) / 4) }.toString() } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 `````` ``````package diophequa import org.junit.Assert.* import org.junit.Test import kotlin.test.assertEquals import java.util.Random class diophanteTest { @Test fun test1() { assertEquals("[[3, 1]]", solEquaStr(5)) } @Test fun test2() { assertEquals("[[4, 1]]", solEquaStr(12)) } @Test fun test3() { assertEquals("[[7, 3]]", solEquaStr(13)) } @Test fun test4() { assertEquals("[[4, 0]]", solEquaStr(16)) } @Test fun test5() { assertEquals("[[9, 4]]", solEquaStr(17)) } @Test fun test6() { assertEquals("[[6, 2]]", solEquaStr(20)) } @Test fun test7() { assertEquals("[[4501, 2250]]", solEquaStr(9001)) } @Test fun test8() { assertEquals("[[2252, 1125]]", solEquaStr(9004)) } @Test fun test9() { assertEquals("[[4503, 2251], [903, 449]]", solEquaStr(9005)) } @Test fun test10() { assertEquals("[[1128, 562]]", solEquaStr(9008)) } @Test fun test11() { val a = "[[4505, 2252], [1503, 750], [647, 320], [505, 248], [415, 202], [353, 170], [225, 102], [153, 60], [135, 48], [103, 20], [97, 10], [95, 2]]" assertEquals(a, solEquaStr(9009)) } @Test fun test12() { assertEquals("[[45001, 22500]]", solEquaStr(90001)) } @Test fun test13() { assertEquals("[]", solEquaStr(90002)) } @Test fun test14() { assertEquals("[[22502, 11250]]", solEquaStr(90004)) } @Test fun test15() { assertEquals("[[45003, 22501], [9003, 4499], [981, 467], [309, 37]]", solEquaStr(90005)) } @Test fun test16() { assertEquals("[[45005, 22502], [15003, 7500], [5005, 2498], [653, 290], [397, 130], [315, 48]]", solEquaStr(90009)) } @Test fun test17() { assertEquals("[[112502, 56249], [56254, 28123], [37506, 18747], [22510, 11245], [18762, 9369], [12518, 6241], [11270, 5615], [7530, 3735], [6286, 3107], [4550, 2225], [3810, 1845], [2590, 1205], [2350, 1075], [1650, 675], [1430, 535], [1150, 325], [1050, 225], [950, 25]]", solEquaStr(900000)) } @Test fun test18() { assertEquals("[[450001, 225000]]", solEquaStr(900001)) } @Test fun test19() { assertEquals("[[225002, 112500], [32150, 16068]]", solEquaStr(900004)) } @Test fun test20() { assertEquals("[[450003, 225001], [90003, 44999]]", solEquaStr(900005)) } @Test fun test21() { assertEquals("[[4500001, 2250000], [73801, 36870]]", solEquaStr(9000001)) } @Test fun test22() { assertEquals("[[2250002, 1125000], [173090, 86532], [132370, 66168], [10402, 4980]]", solEquaStr(9000004)) } @Test fun test23() { assertEquals("[[4500003, 2250001], [900003, 449999], [642861, 321427], [155187, 77579], [128589, 64277], [31107, 15481], [22269, 11033], [4941, 1963]]", solEquaStr(9000005)) } @Test fun test24() { assertEquals("[[45000001, 22500000], [6428575, 3214284], [3461545, 1730766], [494551, 247230]]", solEquaStr(90000001)) } @Test fun test25() { assertEquals("[[22500002, 11250000], [252898, 126360], [93602, 46560], [22498, 10200]]", solEquaStr(90000004)) } //@Test //fun test26() { // assertEquals("[[450000005, 225000002], [150000003, 75000000], [50000005, 24999998], [26470597, 13235290], [8823555, 4411752], [2941253, 1470550]]", solEquaStr(900000009)) //} //@Test //fun test27() { // assertEquals("[[225000004, 112500001], [75000004, 37499999], [3358276, 1679071], [1119604, 559601]]", solEquaStr(900000012)) //} //@Test //fun test28() { // assertEquals("[[4500000021, 2250000010], [155172429, 77586200]]", solEquaStr(9000000041L)) //} @Test fun testA() { println("Random Tests") var u:Long = 0 for (i in 0..5) { val a = randInt(5, 2000) val b = randInt(5, 800) var v = (a * a - 4 * b * b).toLong() if (v < 0) u = -v else u = v val sol = solEquaStrFD(u) assertEquals(sol, solEquaStr(u)) } } companion object { private fun randInt(min:Int, max:Int):Int { return min + (Math.random() * ((max - min) + 1)).toInt() } fun solEquaStrFD(n:Long):String { var res = "[" var i:Long = 1 while (i < Math.sqrt(n.toDouble()) + 1) { if (n % i == 0L) { val p = i + (n / i).toLong() val q = (n / i).toLong() - i if ((p % 2 == 0L) && (q % 4 == 0L)) { val c = "[" + java.lang.Long.toString((p / 2).toLong()) + ", " + java.lang.Long.toString((q / 4).toLong()) + "], " res += c } } i++ } if (res == "[") return "[]" else return res.substring(0, res.length - 2) + "]" } } } ``````