Solving Computer Science Problems with Math

Very often in computer science, there are problems with no obvious "fast" solution. There are computer science techniques to speed up naïve solutions: things like caching intermediate results, using different data structures, and so on. Frequently, though, this isn't enough to arrive at a really good solution to the problem. Many times, we need to use mathematics techniques to simplify the problem, and after doing so, the solution becomes trivially easy to compute.

Pell's Equation

Consider the following ProjectEuler problem:

Consider quadratic Diophantine equations of the form:

\[x^2 - Dy^2 = 1\]

For example, when \(D = 13\), the minimal solution in \(x\) is \(649^2 - 13 \cdot 180^2 = 1\).

It can be assumed that there are no solutions in positive integers when \(D\) is square.

By finding minimal solutions in \(x\) for \(D = \{ 2, 3, 5, 6, 7 \}\), we obtain the following:

\[3^2 - 2 \cdot 2^2 = 1\] \[2^2 - 3 \cdot 1^2 = 1\] \[9^2 - 5 \cdot 4^2 = 1\] \[5^2 - 6 \cdot 2^2 = 1\] \[8^2 - 7 \cdot 3^2 = 1\]

Hence, by considering minimal solutions in \(x\) for \(D \leq 7\), the largest \(x\) is obtained when \(D = 5\).

Find the value of \(D \leq 1000\) in minimal solutions of \(x\) for which the largest value of \(x\) is obtained.

Arguably the main way to solve this problem in a reasonable amount of time is to leverage some techniques from number theory. There are two main papers which give us the tools to solve this problem:

These papers contain proofs that we can solve Pell's equation (which is the formal name for the equation given in the problem above) by finding the convergents of continued fractions. Without too much trouble, we can express these convergents as a series of recurrence relations; more information about this can be found on Wikipedia's article about generalized continued fractions.

With this technique, we have the following recurrence relations:

\[ \begin{aligned} A_0 &= b_0 \\ A_1 &= b_1 b_0 + a_1 \\ A_n &= b_n A_{n - 1} + a_n A_{n - 2} \end{aligned} \qquad \begin{aligned} B_0 &= 1 \\ B_1 &= b_1 \\ B_n &= b_n B_{n - 1} + a_n B_{n - 2} \end{aligned} \]

Simply by finding the values these recurrence relations produce, we can find the answer to the original problem. And this computation is vastly faster than doing something obvious like just trying every combination. In fact, the reason that "it can be assumed that there are no solutions in positive integers when \(D\) is square" is because of the fact that the solutions are described by the convergents of continued fractions. The original problem gave us this hint, but by applying mathematical techniques to solve the problem we could have come across that fact on our own.

Pentagon Numbers

This ProjectEuler problem is another good example of some problem which requires some of these same techniques. The problem reads like this:

Pentagonal numbers are generated by the formula \(P_n = \frac{n (3 n - 1)}{2}\). The first ten pentagonal numbers are:

\[1, 5, 12, 22, 35, 51, 70, 92, 117, 145, \dotsc\]

It can be seen that \(P_4 + P_7 = 22 + 70 = 92 = P_8\). However, their difference, \(70 - 22 = 48\), is not pentagonal.

Find the pair of pentagonal numbers, \(P_j\) and \(P_k\), for which their sum and difference are pentagonal and \(D = |P_k - P_j|\) is minimised; what is the value of \(D\)?

It's possible to solve this by brute force, but it takes a very large amount of computations. It's possible that there are other ways to solve this problem, but one good way is to reduce this problem to a simpler equation.

This approach involves iterating over each pentagonal number (which are easily computed, using the closed formula given in the problem), and then expressing that pentagonal number as the difference of two other pentagonal numbers, and to finally solve the resulting bivariate Diophantine quadratic that results from this expression.

So, as discussed, let's say that we have one particular pentagonal number \(P_d\), which we are expressing as the difference of two other pentagonal numbers, \(P_y\) and \(P_x\). This gives us:

\[ \begin{aligned} P_d &= P_y - P_x \\ P_d &= \frac{y (3 y - 1)}{2} - \frac{x (3 x - 1)}{2} \\ 2 P_d &= 3 y^2 - y - 3 x^2 + x \end{aligned} \]

Next, consider the arbitrary quadratic Diophantine equation in two variables, which we use to give the coefficients in the equation above names:

\[ A x^2 + B x y + C y^2 + D x + E y + F = 0 \]

This equation is simply the equation above, where some of the coefficients are zero. Our next step is to complete the square, so we can factor this equation. In order to do this, we multiply by \(4 A = 4 \cdot 3 = 12\):

\[ 36 y^2 - 12 y - 36 x^2 + 12 x = 24 P_d \]

Next, we finish completing the square on the first two terms by adding and subtracting \(1\):

\[ \begin{aligned} 36 y^2 - 12 y + 1 - 36 x^2 + 12 x - 1 &= 24 P_d \\ (6 y - 1)^2 - 36 x^2 + 12 x - 1 &= 24 P_d \end{aligned} \]

Next, we multiply by \(-1\) so that we can factor the remaining two terms:

\[ \begin{aligned} -(6 y -1)^2 + 36 x^2 - 12 x + 1 &= -24 P_d \\ -(6 y - 1)^2 + (-6 x + 1)^2 &= -24 P_d \end{aligned} \]

Next, let's define \(y^{\prime} = 6 y - 1\) as well as \(x^{\prime} = -6 x + 1\), which allows us to rewrite this equation as:

\[ \begin{aligned} x^{\prime 2} - y^{\prime 2} &= -24 P_d \\ (x^{\prime} + y^{\prime}) (x^{\prime} - y^{\prime}) &= -24 P_d \end{aligned} \]

At this point, we can simply iterate over every pair of factors of \(-24 P_d\), and we solve where \((x^{\prime} + y^{\prime})\) is equal to the larger factor, and \((x^{\prime} - y^{\prime})\) is equal to the smaller factor. If any of these solutions are such that both \(x\) and \(y\) are positive integers, then we have found the indices of the two pentagonal numbers \(P_x\) and \(P_y\) such that \(P_y - P_x = P_d\).

Once we have found these two pentagonal numbers, we can very rapidly test if \(P_x + P_y\) is itself pentagonal, in which case we have arrived at a solution to the original problem.

This solution can be computed much more quickly than the very basic solution of simply testing every possible value. This is a perfect example of how a seemingly computationally hard problem can be reduced to a smaller problem which, when solved, gives us the solution to the original problem.

Summary

The point of all this is simply that it's worth learning mathematics as computer scientists, and it's worth examining problems that seem hard in the context of mathematics to see if they can be reduced to simpler problems. Sometimes, problems can be completely transformed such that it's hard to even see how they are related without understanding the mathematics that got us there. The first problem we discussed is a great example of this: without doing some lengthy number theoretic proofs, it isn't necessarily obvious that the Diophantine equation given in the problem statement has any relation to continued fractions whatsoever.

ProjectEuler provides some good exercises for learning this problem-solving technique. Having solved several of the problems myself, I would highly recommend the problems as a great way to practice mixing mathematics techniques and computer science techniques to solve problems.