4 ms·
It is not computationally tractable to enumerate all triples of integers up to the size required to find the values for 42. So certainly any integer N either i
by ChrisLomont 7y ago
It is not computationally tractable to enumerate all triples of integers up to the size required to find the values for 42.
So certainly any integer N either is or is not the sum of three cubes. Deciding which is the case computationally can be intractable.
Each of the integers in the solution are ~53 bits in length. To enumerate all triples of integers (with plus and minus) requires testing around 2^(53+53+53+1+1+1) = 2^162 items. If you could test one per nanosecond, this is 10^32 years, vastly older than the universe. If you threw 1 trillion such computers at it, it's still 10^23 years, also vastly longer than the age of the universe.
Thus enumeration is simply not possible.
The point of this is they found a solution for 42 after great effort.
- robrenaud 7y agoYou only need to enumerate pairs of integers, the 3rd is then forced (quickly check if it's a cube).
- swolchok 7y ago2^109 nanoseconds is still 150,000 times older than the universe. If you do manage to get a trillion computers, you can now solve the problem in twenty thousand years. It's still intractable.
- ChrisLomont 7y agoYou’re assuming a fixed target. I was enumerating which targets get hit to solve the problem for all cubes up to some fixed size. If you’re assuming a fixed target, you don’t know how large you need to check to find an answer. That 53 bit numbers sufficed for 42 was not known in advance, and is not the bound for other targets.