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

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)

### 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

### [SOLVED] Intuition behind centralizers of Langlands parameters

**2017-04-20 19:51:40****Alexander****270**View**7**Score**1**Answer- Tags: nt.number-theory soft-question langlands-conjectures

#### 2 Answered Questions

### [SOLVED] Intuition behind the Riemann $\zeta$ functional equation

**2017-04-20 17:02:04****Lucian****512**View**1**Score**2**Answer- Tags: nt.number-theory analytic-number-theory riemann-zeta-function functional-equations gamma-function

#### 2 Answered Questions

### [SOLVED] What is wrong with this counterexample to the Weak Bunyakovsky's conjecture and reformulation of Bunyakovsky's conjecture?

**2015-12-09 09:53:59****joro****542**View**0**Score**2**Answer- Tags: nt.number-theory polynomials counterexamples

#### 2 Answered Questions

### [SOLVED] Intuition behind Kronecker's congruence?

**2015-07-17 15:43:36****user76167****608**View**6**Score**2**Answer- Tags: nt.number-theory algebraic-number-theory

#### 1 Answered Questions

### [SOLVED] Counterexample to Pólya's conjecture

**2014-08-25 13:49:33****aziiri****467**View**0**Score**1**Answer- Tags: nt.number-theory computational-complexity

#### 1 Answered Questions

### [SOLVED] Possible counterexample to a theorem assuming Lang's conjecture

**2014-04-27 10:14:58****joro****1328**View**24**Score**1**Answer- Tags: ag.algebraic-geometry elliptic-curves counterexamples

#### 1 Answered Questions

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

**2013-06-01 18:20:35****M.G.****764**View**5**Score**1**Answer- Tags: nt.number-theory prime-numbers

#### 2 Answered Questions

### [SOLVED] Is this a counterexample to a conjecture about independent domination in cartesian graph products?

**2012-09-25 10:45:14****joro****432**View**6**Score**2**Answer- Tags: graph-theory counterexamples

#### 1 Answered Questions

### [SOLVED] Intuition behind the Tamagawa numbers

**2011-07-23 04:17:06****Trust God****2285**View**3**Score**1**Answer- Tags: nt.number-theory ag.algebraic-geometry analytic-number-theory

## 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$$

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

The search was carried out for

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.