Diophantine Equation in Kotlin

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:

// [[45003, 22501], [9003, 4499], [981, 467], [309, 37]] solEquaStr(90005) // [] solEquaStr(90002)
Code language: JavaScript (javascript)

Hint:

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

The solution in Kotlin

Option 1:

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<String>() 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 = "]") }
Code language: Kotlin (kotlin)

Option 2:

package diophequa import kotlin.math.ceil import kotlin.math.pow import kotlin.math.sqrt fun solEquaStr(n: Long): String { val pairs = mutableListOf<Pair<Long, Long>>() 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
Code language: Kotlin (kotlin)

Option 3:

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() }
Code language: Kotlin (kotlin)

Test cases to validate our solution

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) + "]" } } }
Code language: Kotlin (kotlin)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments