Intuition behind counterexample of Euler's sum of powers conjecture

Question

I was stunned when I first saw the article Counterexample to Euler's conjecture on sums of like powers by L. J. Lander and T. R. Parkin:.

How was it possible in 1966 to go through the sheer astronomical space of possibilities, on a CDC 6600 computer?

1) Did Lander and Parkin reveal their strategy?

2) How would you, using all the knowledge that was accessable until 1965, go to search for counter-examples, if you have access to a computer with 3 MegaFLOPS?

(As a comparison, todays home computers can have beyond 100 GigaFLOPS, using GPUs even TeraFLOPs)

Answer 1

The search strategy is laid out in a paper devoted to finding all "small" non-negative solutions of $$x_1^5+\cdots x_n^5=y^5\text{ with }n \leq 6$$

L. Lander & T. Parkin, "A counterexample to Euler's sum of powers conjecture," Math. Comp., v. 21, 1967, pp. 101-103.

The one result was striking enough grab the title and get separate mention in the Bulletin.

The search was carried out for

• $n=6$ and $y \leq 100$ turning up $10$ primitive solutions of which two had $n=5$
• $n=5$ and $y \leq 250$ turning up $3$ more including the unexpected one for $n=4$
• $n=4$ and $y \leq 750$ turning up nothing else new.

That last search covers more than $5000$ times as many cases as going to $133^5.$

The length of the paper hints that the method is fairly simple. Space must have been limited because a table of fifth powers was maintained but not a table of sums $a^5+b^5$ for a meet in the middle attack.

Answer 2

Even simply generating all quadruples $(a, b, c, d)$ with $1 \le a \le b \le c \le d \le 133$ should work fine. There are only about 13 million such quadruples. For each, we need to add together the fifth powers (which can be looked up in a small table) and check whether the result is another fifth power, which we can do by binary search in a table of fifth powers (of size, say, 200 or so). I'm not familiar with the CDC 6600 but it seems like a direct implementation of this kind would finish in under an hour.

There are faster algorithms possible, using the "meet-in-the-middle" method. For example, record all the sums $a^5 + b^5$ for $1 \le a \le b \le 200$ or so, and sort them. Now, for each $1 \le c \le d \le e$, compute $e^5 - c^5 - d^5$ and check whether it is in this table. This algorithm is cubic (up to log factors) in the size of the eventual counterexample, rather than quartic. However, the actual counterexample in this case is small enough that this kind of method seems to be unnecessary.

Answer 3

The longer and more detailed paper reveals that where possible, various modulo constraints were used to shrink the number of tuples to search through further:

L. J. Lander; T. R. Parkin; J. L. Selfridge (1967). "A Survey of Equal Sums of Like Powers". Mathematics of Computation. 21 (99): 446–459. doi:10.1090/S0025-5718-1967-0222008-0