By NicoDean


2019-03-11 16:02:21 8 Comments

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:.

enter image description here

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)

3 comments

@DrBRE 2019-03-27 12:56:24

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

@Aaron Meyerowitz 2019-03-11 18:58:10

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.

@Reid Barton 2019-03-11 16:42:23

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.

@Michael Lugo 2019-03-11 18:50:05

The fact that the authors say they used "direct search" and don't elaborate suggests, to me, that they didn't do anything fancy, and probably used this approach.

@Greg Martin 2019-03-11 22:17:47

One could easily gain a constant factor of 2ish by noting, for example, that all 5th powers are in $\{-1,0,1\}$ modulo $11$; this rules out lots of possible quadruples.

Related Questions

Sponsored Content

0 Answered Questions

Alternating sum of powers

  • 2018-03-31 09:30:51
  • Fedor Petrov
  • 220 View
  • 4 Score
  • 0 Answer
  • Tags:   nt.number-theory

1 Answered Questions

2 Answered Questions

[SOLVED] Intuition behind Kronecker's congruence?

1 Answered Questions

[SOLVED] Counterexample to Pólya's conjecture

1 Answered Questions

1 Answered Questions

[SOLVED] Goldbach's conjecture and Euler's idoneal numbers

1 Answered Questions

Sponsored Content