Re:Counterexample to Euler's conjecture on sums of like powers
by gshubert17 on Saturday June 11, 2016 @03:11PM
(#11884839)
I computed an array of fifth powers, up to 200, then had four nested loops. Using python3 on a 2.66-GHz Core 2 Duo, it took 48 seconds to find the reported numbers. If there had been no solutions, it would have taken only a couple of seconds longer.
Re:Counterexample to Euler's conjecture on sums of like powers
by Someone on Sunday June 12, 2016 @02:34PM
(#11889533)
That's modern hardware, where recomputing n^5 + m^5 when needed may on average be faster than doing the lookup with its risk of a cache miss.
That CDC6600 dates from a time where register access wasn't much faster (if it was faster at all. https://en.m.wikipedia.org/wiki/CDC_6600#Description: For instance, a processor might take 15 cycles to multiply two numbers, while each memory access took only one or two) than reading from memory, and integer multiplication took >1 cycle (https://en.m.wikipedia.org/wiki/CDC_6600#Description: in addition to the clock being faster, the simple processor executed instructions in fewer clock cycles; for instance, the CPU could complete a multiplication in ten cycles.)
- compute S0 = {n^5 | 1 < n <= 1320} (3960 multiplications)
- compute S1 = {n^5 | 1 < n <= 1000} (zero multiplications)
- compute S2 = {s+t | s,t ∈ S1} (500,500 additions)
- compute S4 = {s+t | s,t ∈ S2} (around 10^11 additions)
- compute the intersection of S0 with 4
You don't have to store S4, so 2 megabytes of memory or so should suffice. 10^11 operations likely was out of reach for the CDC600, though.
To speed up things, do the above for numbers up to 100 or so using modulo arithmetic. That gives you candidate solutions modulo your word size. That way, you don't have to compute large parts of S4.