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.


val .fun = f [.b, .b x .c + .a]
 
val .solvePell = f(.n) {
    val .x = truncate .n ^/ 2
    var .y, .z, .r = .x, 1, .x x 2
    var .e1, .e2, .f1, .f2 = 1, 0, 0, 1
 
    for {
        .y = .r x .z - .y
        .z = (.n - .y x .y) \ .z
        .r = (.x + .y) \ .z
        .e1, .e2 = .fun(.e1, .e2, .r)
        .f1, .f2 = .fun(.f1, .f2, .r)
        val .b, .a = .fun(.e2, .f2, .x)
        if .a^2 - .n x .b^2 == 1: return [.a, .b]
    }
}
 
val .C = f(.x) {
    # format number string with commas
    var .neg, .s = ZLS, toString .x
    if .s[1] == '-' {
        .neg, .s = "-", rest .s
    }
    .neg ~ join ",", split -3, .s
}
 
for .n in [61, 109, 181, 277, 8941] {
    val .x, .y = .solvePell(.n)
    writeln $"x² - \.n;y² = 1 for:\n\tx = \.x:.C;\n\ty = \.y:.C;\n"
}
 