Skip navigation

Category Archives: Computer Science

Offtonic Pell Solver has been released!

(Part 1)

We’re solving x^2 – Dy^2 = N.  We’ve gotten the very easy cases out of the way: N = 0, D = 0.  We’ve gotten the easy cases out of the way: D < 0, D = d^2.  This leaves only the situation where D is a non-square positive integer and N is nonzero.  As we will see, this one is legitimately complicated.  A Pell equation is one where N = 1.  Such an equation always has a solution.  Now let’s suppose (x,y) is a solution to x^2 – Dy^2 = N and (r,s) is a solution to x^2 – Dy^2 = 1.  If u + v sqrt(D) = (r + s sqrt(D))(x + y sqrt(D)), (u,v) will also be a solution to x^2 – Dy^2 = N.  In other words, you can combine a solution of the original equation with a solution to the N = 1 equation to create a new solution of the original equation.  And you can do this forever: if a solution exists, there is an infinite number of them.  Luckily, it turns out that those infinite solutions are organized: there is a finite number of fundamental solutions, and each of those can generate an infinity of solutions by combining with the N = 1 solution.  Our task, then, is to (a) find the N = 1 solution (the N = -1 solution is important as well, if it exists), (b) find the fundamental solutions, and (c) combine them.  We can do (c) very easily using the formula above; the challenges are (a) and (b).  But first, there’s an algorithm called the PQa algorithm, and there are various equivalent formulations of it.  The one I will show is the one from John P. Robertson’s paper:

Read More »

Offtonic Pell Solver has been released!

(Part 2)

For my inaugural instructional post, I want to tackle a mathematical problem: solving Pell-type equations (with a computer, not by hand).  What do I mean?  I mean equations that look like this:

x^2 – Dy^2 = N

where D and N are integers and x and y are nonnegative integers.  This makes it a quadratic Diophantine equation, and as it turns out, they’re not so easy to solve.  I came across some of these critters in a Project Euler problem a while ago (no, I won’t tell you which one), and I looked up how to solve them.  Well, maybe my Google-fu is not strong, but I didn’t find anything easy to understand.  There were a few incomplete references, a few references that didn’t explain much, and some papers with quite a bit of theory.  I eventually found this paper (Solving the generalized Pell equation x^2 − Dy^2 = N, John P. Robertson, 2004) that made sense, and I distilled it into an algorithm.  This method is mostly based on Robertson’s.

Read More »