Search for specific values

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)

Interactive Section

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

Other pages

(c) John Whitehouse 2021