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)
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 = "]")
}
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
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()
}
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) + "]"
}
}
}