This post was inspired by a joke from Futurama in which two robots laugh at the fact that their serial numbers (3370318 and 2716057) are both expressible as the sum of two cubes. I’ll explain how to express these numbers as sums of two cubes and discuss some of the relevant mathematics.

Modular Arithmetic

Modular arithmetic is a basic yet powerful technique in number theory. Whereas usual arithmetic involves the integers, modular arithmetic involves the remainders of integers after division by an integer $m$ . Integers that have the same remainder after division by $m$ are equivalent in the following sense: we say that $a$ and $b$ are congruent modulo $m$ if $a - b$ is a multiple of $m$ . This is written $a \equiv b \pmod{m}$ . The set

$\{\dots, a - 2m, a - m, a, a + m, a + 2m, \dots\}$

(that is, the set of all integers that are congruent to $a$ modulo $m$ ) is called the congruence class of $a$ .

Everyone who can tell time has used modular arithmetic. Hours are measured modulo 12 (or modulo 24 in military time). 5 hours past 10:00 is 3:00 rather than 15:00. We can write $15 \equiv 3 \pmod{12}$ to express this as a congruence relation.

It turns out to be very helpful to consider cubes modulo 9. This is because every cube is congruent to either 0, 1, or -1 modulo 9. You can check this by cubing 0, 1, 2, 3, 4, 5, 6, 7, and 8 (the only possible remainders after division by 9). For example, $8^3 = 512 \equiv -1 \pmod{9}$ .

Because cubes can only be congruent to 1, 0, or -1 modulo 9, the sum of two cubes can only be -2, -1, 0, 1, or 2 modulo 9. Therefore any integer that is congruent to 3, 4, 5, or 6 modulo 9 cannot be expressed as the sum of two cubes.

A similar argument shows that any integer that is congruent to 3 or 4 modulo 7 is not expressible as the sum of two cubes. You can check this by cubing 0, 1, 2, 3, 4, 5, and 6.

Finding two cubes

If an integer $n$ is in the right congruence classes modulo 9 and modulo 7, we would like to know if it is possible to express $n$ as the sum of two cubes. To do this, we will use the following factorization.

$a^3 + b^3 = (a + b)(a^2 - ab + b^2)$

This reduces the problem of finding two cubes that add up to $n$ to finding a factorization of the form $n = (a + b)(a^2 - ab + b^2)$ . Note that $a + b < a^2 - ab + b^2$ when $(a,b)$ is outside the ellipse $a^2 - ab + b^2 = a + b$ . Because of this, we may assume that $a + b$ is the smaller divisor whenever $n$ is large enough. I leave it to the reader to verify that $n \geq 8$ is sufficient.

We can simplify our computations by changing coordinates.

$\begin{align*}c &= a + b \\d &= a - b\end{align*}$

The equation $n = (a + b)(a^2 - ab + b^2)$ becomes $n = c \left(\frac{c^2 + 3d^2}{4}\right)$ . Solving for $d$ in terms of $n$ and $c$ , we obtain

$d = \pm\sqrt{\frac{4n - c^3}{3c}}$

If $a$ and $b$ are integers, then so are $c = a + b$ and $d = a - b$ . It is also true that if $c$ and $d$ are integers then $a$ and $b$ are integers, but this is trickier to show. We know that $\frac{c^2 + 3d^2}{4}$ is an integer, and so $c^2 + 3d^2$ must be divisible by 4. This is only possible if $c$ and $d$ are either both even or both odd. (This is yet another helpful application of modular arithmetic: even integers are exactly those that are congruent to 0 modulo 2; odd integers are those which are congruent to 1 modulo 2). From the equations $a = \frac{c + d}{2}$ and $b = \frac{c - d}{2}$ we see that $a$ and $b$ are integers.

The upshot of all this is that we can check whether a given integer is a sum of two cubes by (1) finding all factorizations $n = cd$ where $c \leq d$ and (2) checking whether $\sqrt{\frac{4n - c^3}{3c}}$ is an integer. Here’s an implementation in Python.

In [1]:

import math

In [2]:

def print_cube_sum(n,a,b):
    # Prints n = a^3 + b^3 with appropriate parentheses if a or b is negative.
    # This only supports nonnegative n.
    
    # Make sure a is the smaller of a and b so that b > 0.
    if a > b:
        a, b = b, a
    
    s = str(n) + ' = ' + str(b) + '^3'
    
    if a < 0:
        s += ' + (' + str(a) + ')^3'
    elif a > 0:
        s += ' + ' + str(a) + '^3'
    
    print(s)
    
    return

In [3]:

def find_two_cubes(n):
    if n % 9 not in {0, 1, 2, 7, 8}:
        return
    if n % 7 not in {0, 1, 2, 5, 6}:
        return

    # Find divisors c such that n = cd and c <= d.
    for c in range(1, math.floor(math.sqrt(n))+1):
        if n % c == 0 and 4*n - c**3 >= 0:
            d = math.sqrt((4*n - c**3)/(3*c))
            if d.is_integer():
                # If d is an integer, then a and b are integers and n = a^3 + b^3.
                a = int((c - d) // 2)
                b = int((c + d) // 2)
                print_cube_sum(n,a,b)

    return

Let’s test this for the numbers 1 through 100, and also for Flexo and Bender’s serial numbers.

In [4]:

for n in range(1,101):
    find_two_cubes(n)

1 = 1^3
7 = 2^3 + (-1)^3
8 = 2^3
9 = 2^3 + 1^3
16 = 2^3 + 2^3
19 = 3^3 + (-2)^3
26 = 3^3 + (-1)^3
27 = 3^3
28 = 3^3 + 1^3
35 = 3^3 + 2^3
37 = 4^3 + (-3)^3
54 = 3^3 + 3^3
56 = 4^3 + (-2)^3
61 = 5^3 + (-4)^3
63 = 4^3 + (-1)^3
64 = 4^3
65 = 4^3 + 1^3
72 = 4^3 + 2^3
91 = 6^3 + (-5)^3
91 = 4^3 + 3^3
98 = 5^3 + (-3)^3

In [5]:

# Express Flexo's serial number as a sum of two cubes.
find_two_cubes(3370318)

3370318 = 119^3 + 119^3

In [6]:

# Express Bender's serial number as a sum of two cubes.
find_two_cubes(2716057)

2716057 = 952^3 + (-951)^3

Notice that the algorithm failed to find the expression $2 = 1^3 + 1^3$ . This is because of our earlier assumption that $a + b < a^2 - ab + b^2$ . When $a = b = 1$ , the inequality is false. This is the only special case that our algorithm missed.

It’s interesting to note that some integers that are in the right congruence classes modulo 9 and modulo 7 are not expressible as the sum of two cubes. 20, for example, is congruent to 2 modulo 9 and -1 modulo 7, yet it is not expressible as a sum of two cubes.

Broughan’s Theorem

A very nice paper by Kevin A. Broughan explains why some numbers (like 20) aren’t expressible as a sum of two cubes. Broughan’s main theorem is this:

The equation $n = a^3 + b^3$ has a solution in positive integers $a$ and $b$ if and only if the following three conditions are satisfied:

There exists a divisor $m$ of $n$ with $n^{\frac{1}{3}} \leq m \leq 2^{\frac{2}{3}}n^{\frac{1}{3}}$ such that
for some positive integer $\ell$ , $m^2-\frac{n}{m} = 3\ell$ and such that
$m^2 - 4\ell$ is a perfect square.