Diophantine Equation in Kotlin

1
2
3
4
5

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

// []
solEquaStr(90002)

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

 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<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

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()
}

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