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
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
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 :
=>−3d^3+12(n+z^3)>=0 (as 'd' is positive)
=>d<=(4(n+z^3))^[1/3]~=1.6z (for small n)
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:
(c) John Whitehouse 2021