Diophantine Equation in Kotlin | Learn to Grasp Software program Engineering, DevOps and Cloud

The problem

In arithmetic, a Diophantine equation is a polynomial equation, normally with two or extra unknowns, such that solely the integer options are sought or studied.

On this problem we wish to discover all integers x, y (x >= 0, y >= 0) options of a diophantine equation of the shape:

x² – 4 * y² = n

(the place the unknowns are x and y, and n is a given constructive quantity) in lowering order of the constructive x_i.

If there isn’t a resolution return [] or "[]" or "". (See “RUN SAMPLE TESTS” for examples of returns).

Examples:

// [[45003, 22501], [9003, 4499], [981, 467], [309, 37]]
solEquaStr(90005)

// []
solEquaStr(90002)

Trace:

x² – 4 * y² = (x – 2*y) * (x + 2*y)

The answer in Kotlin

Possibility 1:

bundle diophequa
import kotlin.math.sqrt

enjoyable solEquaStr(n:Lengthy):String {
    if ( (n % 2 == 0L) and  (n/2 % 2 == 1L)) return "[]"
    val decrease = if (n % 2 == 0L) {2} else {1}
    val restrict = sqrt(n.toDouble()).toInt()
    val strings = mutableListOf<String>()
    for (a in decrease..restrict step 2) {
        if (n % a != 0L) proceed
        val b = n/a
        if (((a+b) % 2 != 0L) or ((b-a) % 4 != 0L)) proceed
        val x = (a+b)/2
        val y = (b-a)/4
        strings.add(listOf(x,y).joinToString(prefix = "[",postfix = "]"))
        }
    return strings.joinToString(prefix = "[",postfix = "]")
}

Possibility 2:

bundle diophequa

import kotlin.math.ceil
import kotlin.math.pow
import kotlin.math.sqrt

enjoyable solEquaStr(n: Lengthy): String {
    val pairs = mutableListOf<Pair<Lengthy, Lengthy>>()
    val (low, excessive) = ceil(sqrt(n.toDouble())).toLong() to ceil(n.toDouble() / 2).toLong()
    (excessive 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]" }
}

enjoyable findY(n: Lengthy, x: Lengthy) = sqrt((x.toDouble().pow(2) - n) / 4)

enjoyable Double.isInteger() = this == Math.ground(this) && !this.isInfinite()
Finest Practices1Clever0
0ForkLink

Possibility 3:

bundle diophequa

enjoyable solEquaStr(n:Lengthy):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()
}

Check circumstances to validate our resolution

bundle diophequa

import org.junit.Assert.*
import org.junit.Check
import kotlin.check.assertEquals
import java.util.Random

class diophanteTest {
  @Check
  enjoyable test1() {
    assertEquals("[[3, 1]]", solEquaStr(5))
  }
  @Check
  enjoyable test2() {
    assertEquals("[[4, 1]]", solEquaStr(12))
  }
  @Check
  enjoyable test3() {
    assertEquals("[[7, 3]]", solEquaStr(13))
  }
  @Check
  enjoyable test4() {
    assertEquals("[[4, 0]]", solEquaStr(16))
  }
  @Check
  enjoyable test5() {
    assertEquals("[[9, 4]]", solEquaStr(17))
  }
  @Check
  enjoyable test6() {
    assertEquals("[[6, 2]]", solEquaStr(20))
  }
  @Check
  enjoyable test7() {
    assertEquals("[[4501, 2250]]", solEquaStr(9001))
  }
  @Check
  enjoyable test8() {
    assertEquals("[[2252, 1125]]", solEquaStr(9004))
  }
  @Check
  enjoyable test9() {
    assertEquals("[[4503, 2251], [903, 449]]", solEquaStr(9005))
  }
  @Check
  enjoyable test10() {
    assertEquals("[[1128, 562]]", solEquaStr(9008))
  }
  @Check
  enjoyable 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))
  }
  @Check
  enjoyable test12() {
    assertEquals("[[45001, 22500]]", solEquaStr(90001))
  }
  @Check
  enjoyable test13() {
    assertEquals("[]", solEquaStr(90002))
  }
  @Check
  enjoyable test14() {
    assertEquals("[[22502, 11250]]", solEquaStr(90004))
  }
  @Check
  enjoyable test15() {
    assertEquals("[[45003, 22501], [9003, 4499], [981, 467], [309, 37]]", solEquaStr(90005))
  }
  @Check
  enjoyable test16() {
    assertEquals("[[45005, 22502], [15003, 7500], [5005, 2498], [653, 290], [397, 130], [315, 48]]", solEquaStr(90009))
  }
  @Check
  enjoyable 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))
  }
  @Check
  enjoyable test18() {
    assertEquals("[[450001, 225000]]", solEquaStr(900001))
  }
  @Check
  enjoyable test19() {
    assertEquals("[[225002, 112500], [32150, 16068]]", solEquaStr(900004))
  }
  @Check
  enjoyable test20() {
    assertEquals("[[450003, 225001], [90003, 44999]]", solEquaStr(900005))
  }
  @Check
  enjoyable test21() {
    assertEquals("[[4500001, 2250000], [73801, 36870]]", solEquaStr(9000001))
  }
  @Check
  enjoyable test22() {
    assertEquals("[[2250002, 1125000], [173090, 86532], [132370, 66168], [10402, 4980]]", solEquaStr(9000004))
  }
  @Check
  enjoyable test23() {
    assertEquals("[[4500003, 2250001], [900003, 449999], [642861, 321427], [155187, 77579], [128589, 64277], [31107, 15481], [22269, 11033], [4941, 1963]]", solEquaStr(9000005))
  }
  @Check
  enjoyable test24() {
    assertEquals("[[45000001, 22500000], [6428575, 3214284], [3461545, 1730766], [494551, 247230]]", solEquaStr(90000001))
  }
  @Check
  enjoyable test25() {
    assertEquals("[[22500002, 11250000], [252898, 126360], [93602, 46560], [22498, 10200]]", solEquaStr(90000004))
  }
  //@Check
  //enjoyable test26() {
  //  assertEquals("[[450000005, 225000002], [150000003, 75000000], [50000005, 24999998], [26470597, 13235290], [8823555, 4411752], [2941253, 1470550]]", solEquaStr(900000009))
  //}
  //@Check
  //enjoyable test27() {
  //  assertEquals("[[225000004, 112500001], [75000004, 37499999], [3358276, 1679071], [1119604, 559601]]", solEquaStr(900000012))
  //}
  //@Check
  //enjoyable test28() {
  //  assertEquals("[[4500000021, 2250000010], [155172429, 77586200]]", solEquaStr(9000000041L))
  //}
  @Check
  enjoyable testA() {
    println("Random Exams")
    var u:Lengthy = 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 {
    personal enjoyable randInt(min:Int, max:Int):Int {
      return min + (Math.random() * ((max - min) + 1)).toInt()
    }
    enjoyable solEquaStrFD(n:Lengthy):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.size - 2) + "]"
    }
  }
}