I only wish they'd described the method they used to find the counterexample.
The CDC 6600 was a pretty hardcore machine; it was Seymour Cray's first design at his Chippewa Falls skunk works, according to Wikipedia. Would definitely be interesting to know how long their solution took.
- 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.
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.)