[Math] First 30 solutions of Pell’s equation.

diophantine equationspell-type-equations

$k^2 – 5z^2 = 1 (1)$

The equation (1) is a Pell equation where $D = 5$ and the first solution $\{k, z\} =\{9, 4\} = \{p, q\} (2)$

$k_n = \dfrac{(p + q\sqrt{D})^n + (p – q\sqrt{D})^n}{2} ;
z_n = \dfrac{(p + q\sqrt{D})^n – (p – q\sqrt{D})^n}{2\sqrt{D}} (3)$

Where n is index of a solution. Replace p and q in (2) with (3)

$k_n = \dfrac{(9 + 4\sqrt{5})^n + (9 – 4\sqrt{5})^n}{2} ;
z_n = \dfrac{(9 + 4\sqrt{5})^n – (9 – 4\sqrt{5})^n}{2\sqrt{5}} (4)$

Equations (35,36) from Pell's equation on Wolfram

I wrote a small Python program to calculate 30 solutions. However, the first 12 solutions are correct then all others are incorrect.

import math
def pell(u,v,D,nMaxUpperBound=30):
    lstResult = []
    a = u + v*math.sqrt(D)
    b = u - v*math.sqrt(D)
    for i in range (1, nMaxUpperBound, 1) :
        k = int(round((math.pow(a, i) + math.pow(b, i))/2))
        z = int(round((math.pow(a, i) - math.pow(b, i))/(2 * math.sqrt(D))))
        if k**2 - D*z**2 == 1:
            lstResult.append((k,z))
        else:
            print("failed. i = ", i, "k,z => (%d,%d)" % (k,z))
    return lstResult
lstResult = pell(9, 4, 5)
print(lstResult)

What should I do to improve the program or use a different approach to calculate all 30 solutions?

Best Answer

Floating point precision is not sufficient for the larger solutions. You should probably look at using a recursive definition for the $k_n$ and $z_n$. They should satisfy $a_{n+2}=18a_{n+1}-a_{n}$ (derived from the minimum polynomial of $9\pm4\sqrt{5}$). Try to find a tail recursive solution, and you shouldn't run into problems until you overflow the ints.

Related Question