There is a numberphile video on youtube which talks about how they solved the problem of identifying integer solutions to equations likex^3+y^3+z^3=33. I found this quite interesting, but the video didn't go into the details of how they actually implemented the algorithm, so I thought I'd give it a go and see how it pans out. The simplification they made was that rather than search for any small sum they'd pick a single value and focus on that. At the time 33 was the smallest unsolved value. To get a small value like 33 using cubes greater than 3 at least one of x, y and z must be negative.

Since this video a follow-up video provides a solution for 42. It uses 17 digit numbers. This is the last possible number smaller than 100 to be solved.

So we start by looking for solutions of x^3+y^3-z^3=n. We could also search for solutions of x^3+y^3-z^3=-n (as this rearranges to z^3-x^3-y^3=n), but when I experimented using the tester below it always seemed to find both cases at the same time.

This rearranges to (x+y)(x^2-xy+y^2)=n+z^3.

We can set x+y=d, giving

x^2-xy+y^2=(n+z^3)/d, or:

x^2-dx+d^2=(n+z^3)/d.

The video argued that this is essentially a one-dimensional search (for z) as there are only a few plausible 'd' values. This wasn't justified in the video so I thought I'd start by verifying that.

The first thing you'd notice is that, as we are looking for integers, 'd' must divide n+z^3, but n+z^3 could be a very large number with a large number of factors, and finding factors gets harder as the numbers get bigger. However, let's continue. For 'd' values that do divide n+z^3 we have to solve the quadratic equation:

3x^2-3dx+d^2-(n+z^3)/d=0 for x.

Which is equvalent to the traditional quadratic equation
ax^2+bx+c=0 with

a=3,

b=−3d and

c=d^2-(n+z^3)/d.

For this to have integer roots the expression b^2-4ac must be a square number, which means that at least it must be positive, so :

b^2-4ac=9d^2-12(d^2-(n+z^3)/d)>=0

=>−3d^2+12(n+z^3)/d>=0

=>−3d^3+12(n+z^3)>=0 (as 'd' is positive)

=>12(n+z^3)>=3d^3

=>4(n+z^3)>=d^3

=>d<=(4(n+z^3))^[1/3]~=1.6z (for small n)

To be an integer 3d^3 must be a multiple of 4, so 'd' must be even. There are some other optimisations that can be applied, see the Notes section below, but these aren't used in the code associated with this page.

Let's see how this works in reality. Note: This section is just to show you how the algorithm works, you won't be able to find any new solutions. In the accompanying video you'll see that the components that add up to 33 have 16 digits. This isn't really reachable using the built in numbers of javascript as the algorithm has a z^3 term, which will overflow for 'z' values around 1 million. Also searching 10^17 potential values will probably take longer than the lifetime of your computer.

in the controls below "Target" is the 'n' value you are looking for (33 in the video) and "Max Z" is the largest potential 'z' value that will be tested. The "Verbose" button will generate output showing the workings described above, and will generate a lot of output. The "Solve" will just show the solutions found, and "Unique" will eliminate duplicate solutions by arranging x, y and z so that x>y>z.

720 is an interesting target, also try comparing the results for n and −n.

Target: Max Z:

result

If you calculate the sequence z^3 modulo 9 you get [1,8,0,1,8,0,1,8,0,...]. This repeats indefinitely. You can show this by considering the expression (3n+k)^3 mod 9, where 0<=k<=2. This expands to:

(3n)^3+3.(3n)^2k+3.(3n)k^2+k^3 mod 9.

The first three terms are all multiples of 9, so the remainder will be k^3 mod 9 which is [1,8,0] as we showed above. The possible remainders when x^3+y^3+z^3 is divided by 9 can be obtained by adding all the permutations of three numbers taken from this list, which are: [0,1,2,3,8,9,10,16,17,24], which modulo 9 become [0,1,2,3,8,0,1,7,8,6].

If you expand these sums into a table:

k1,k2,k3 | 0,0 | 0,1 | 0,8 | 1,0 | 1,1 | 1,8 | 8,0 | 8,1 | 8,8 |
---|---|---|---|---|---|---|---|---|---|

0 | 0 | 1 | 8 | 1 | 2 | 0 | 8 | 0 | 7 |

1 | 1 | 2 | 0 | 2 | 3 | 1 | 0 | 1 | 8 |

8 | 8 | 0 | 7 | 0 | 1 | 8 | 7 | 8 | 6 |

And arrange them according to the total we can infer some additional constraints on 'z'.

Total | Combinations | Count | Constraints on 'z' |
---|---|---|---|

0 | (0,0,0), (0,1,8) | 7 | none |

1 | (0,0,1), (1,1,8) | 6 | none |

2 | (0,1,1) | 3 | z mod 3 can't be 2 |

3 | (1,1,1) | 1 | z mod 3 must be 1 |

4 | 0 | impossible | |

5 | 0 | impossible | |

6 | (8,8,8) | 1 | z mod 3 must be 2 |

7 | (0,8,8) | 3 | z mod 3 can't be 1 |

8 | (0,0,8), (1,8,8) | 6 | none |

(c) John Whitehouse 2021