Pell's equation   (also called the Pell–Fermat equation)   is a   Diophantine equation   of the form:

   x2   -   ny2   =   1  
with integer solutions for   x   and   y,   where   n   is a given non-square positive integer.



Task requirements

   find the smallest solution in positive integers to Pell's equation for   n = {61, 109, 181, 277}.


See also

   Wikipedia entry: Pell's equation.


def pellFermat(n: Int): (BigInt,BigInt) = {
  import scala.math.{sqrt, floor}
 
  val x = BigInt(floor(sqrt(n)).toInt)
 
  var i = 0
 
  // Use the Continued Fractions method
  def converge(y:BigInt, z:BigInt, r:BigInt, e1:BigInt, e2:BigInt, f1:BigInt, f2:BigInt ) : (BigInt,BigInt) = {
 
    val a = f2 * x + e2
    val b = f2
 
    if (a * a - n * b * b == 1) {
      return (a, b)
    }
 
    val yh = r * z - y
    val zh = (n - yh * yh) / z
    val rh = (x + yh) / zh
 
    converge(yh,zh,rh,e2,e1 + e2 * rh,f2,f1 + f2 * rh)
  }
 
  converge(x,BigInt("1"),x << 1,BigInt("1"),BigInt("0"),BigInt("0"),BigInt("1"))
}
 
val nums = List(61,109,181,277)
val solutions = nums.map{pellFermat(_)}
 
{
  println("For Pell's Equation, x\u00b2 - ny\u00b2 = 1\n")
  (nums zip solutions).foreach{ case (n, (x,y)) => println(s"n = $n, x = $x, y = $y")}
}