Continued Fractions, Pell’s Equation and Scary Numbers.

This is Pell’s equation:

x^2 -ny^2 = 1

where n is a positive integer that isn’t a perfect square. Only integer solutions for x and y are sought and if n is not a perfect square then there are infinitely many integer solutions.

It can be shown that the convergents of the continued fraction (CF) for the square root of n contains a solution known as the Fundamental Solution (FS). In practice this fundamental solution is the first convergent that satisfies the equation under consideration. Once this solution is known then all other solutions can be calculated from a simple recurrence relationship. i.e. If the fundamental solution is (x1, y1) then

x_{k+1} = x_1 x_k + n y_1 y_k

y_{k+1} = x_1 y_k + y_1 x_k

Note that a more rigorous treatment of the above formulae can be found on WolframMathWorld and on Wikipedia.

and now a bit of Haskell… 🙂

First we’ll look at getting the FS and from that we can derive all others. To determine the FS we first calculate the continued fraction for root n in list format. We then get the convergents from that list. This allows us look at each convergent until we find one that is a solution of Pell’s equation for the given n. Expressing this in Haskell gives…

The function notPellSolution is self explanatory. Function solvePell does as described above and uses dropWhile with the convergents (which are Fractions) deconstructed into a numerator and a denominator. And of course dropWhile stops once a a solution is found. So, for example we can do

which gives us solutions for n=1 to 30 excluding perfect squares.

Now that we has the FS we can determines all solutions using the recurrence relationship in (2) which translates quite neatly into Haskell as

This will generate an infinite list so we need to take only what we need. For example

The number 313 is quite interesting as its FS is quite a large number and of course subsequent solutions are larger.

In the tenth solution x is a 169 digit number and y has 168 digits!

I find it stunning that something simple and benign looking as

x^2 -313y^2 = 1

hides such monstrous numbers! We can open it up even more with a couple of helper functions. One to count the number of digits in a number and one to get the nth solution as (x, y) and then count the digits in each. Like this

We can now use the above on this innocent looking equation 🙂

x^2 -2y^2 = 1

For the 10 000th solution…

showing that x and y both have over 7000 digits.

Even bigger, 1 000 000th solution…

showing that x and y each have over three quarters of a million digits each! These aren’t numbers, they’re beasts from the Abyss!

The last time I counted, the universe had around 10^80 atoms – give or take – that’s an 81 digit number. And yet

x^2 -2y^2 = 1

hides numbers that are truly incomprehensible.

All of the code is in Github.

Thanks for reading…!

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top