Positive integer solutions of $a^3 + b^3 = c$

Is there any fast way to solve for positive integer solutions of $$a^3 + b^3 = c$$ knowing $c$?
My current method is checking if $c – a^3$ is a perfect cube for a range of numbers for $a$, but this takes a lot of time for larger numbers. I know $c = (a+b)(a^2-ab+b^2)$, but I can’t think of a way this would speed up the process. Factoring numbers can be done fairly quickly but then the values of $a$ and $b$ have to be chosen. This is for a previous question I had about Fibonacci numbers. Any relevant literature is appreciated.

Solutions Collecting From Web of "Positive integer solutions of $a^3 + b^3 = c$"

A very fast way to see that a positive integer $c$ is not the sum of two cubes are modular constraints. The equation $a^3+b^3=c$ has no integer solutions if $c$ satisfies one of the following congruences:

(1) \quad c\equiv 3,4 \mod 7

(2) \quad c\equiv 3,4,5,6 \mod 9

(3) \quad c\equiv 3,4,5,6,10,11,12,13,14,15,17,18,21, 22, 23, 24, 25, 30, 31, 32, 33, 38, 39, 40,
41, 42, 45, 46, 48, 49, 50, 51, 52, 53, 57,
58, 59, 60 \mod 63

On the other hand, there are intrinsic properties of $c$ known, such that $c$ is the sum of two squares:

Theorem (Broughan 2003): Let $c$ be a positive integer. Then the equation $c=a^3+b^3$ has solutions in positive integers if and only if the following conditions are satisfied:

1.) There exists a divisor $d\mid c$ with $c^{1/3}\le d\le 2^{2/3}c^{1/3}$ such that

2.) for some positive integer $l$ we have $d^2-c/d=3l$ such that

3.) the integer $d^2-4l$ is a perfect square.

$c=(a+b)(a^2−ab+b^2)$ should actually be quite helpful. After factoring $c$, you find all possibly ways of writing $c = xy$. Let $x = a + b$ or $b = x – a$, so

a^2-ab+b^2 = a^2 – a(x-a) + (x-a)^2 = 3a^2 – 3ax + x^2 = y

Solve this quadratic equation for a and check that a is an integer.

Obviously many factors need not be examined: If we keep the sum $x = a+b$ fixed, then $a^3 + b^3$ is between $x^3/4$ and $x^3$, so $x$ must be between $c^{1/3}$ and $(4c)^{1/3}$.

After reading previous posts, this seems to be a published result, cited as (Broughan, 2003). Had a look at the paper. Oh well, you can sure make this complicated.

For not very large c, say $c < 10^9$, brute force may be quicker: Let a = 0, b = $c^{1/3}$, rounded down. As long as $a^3 + b^3 < c$ increase a by 1. If $a^3 + b^3 = c$ note that you found a solution. Then decrease b by 1, repeat until $a > b$.

You might as well concentrate on the case that $a$ and $b$ are relatively prime. This means that $a^{2}+b^{2}-ab$ must either be a product of primes all congruent to $1$ (mod $3$), or else $3$ times such a product. Hence if you write $c = 3^{m-1}d\cdot3f$, where $3^{m}$ is the exact power of $3$ dividing $c$ and $d$ is the product of all prime divisors of $c$ which are congruent to $2$ (mod $3$) (including multiplicities), then if $m=0$, we need to express $f$ in the form $x^{2}+y^{2}-xy$ for integers $x$ and $y$ (and this can be done). If $m >0$, we need to express $3f$ in the form $x^{2}+y^{2}-xy$ for integers $x$ and $y$ (and this can be done). For every such expression (and the number of such expressions can be calculated precisely from the rational prime factorization of $f$), we need to check whether or not $d = x+y$ when $m = 0$, or $3^{m-1}d = x+y$ when $m >0$.

While this is theoretically correct, I can’t claim that it is fast or efficient (it depends on factorization properties of the Eisenstein integers $\mathbb{Z}[\omega]$, where $\omega = e^{\frac{2 \pi i}{3}}\!\!$). However, let’s analyse $c = 468 = 9 \times 52$. According to the above method, we have to express $39$ in the form $x^{2}+y^{2}-xy$ for integers $x$ and $y$ and we should have $x+y = 12$ if we are to obtain $x^{3}+y^{3} = 468$. At this stage there are few possibilities to check and up to symmetry, the solution is $x = 5,y = 7$. It might be helpful to note that in general, we need $(3^{m-1}d)^{2} > 3f$ when $3$ divides $c$ and $d^{2} > f$ when $3$ does not divide $c$, if there is to be any chance of having solution to $c = a^{3}+b^{3}$, with $a$ and $b$ both positive.