Proofs of Existence and Optimality · Difficult Problems in Number Theory (Optional)

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

As a counterexample to Euler's hypothesis, one may take the following set of numbers: \[a=95800,\ b=217519,\ c=414560,\ d=422481\ .\] It is easy to verify its correctness: 

print(95800 ** 4 + 217519 ** 4 + 414560 ** 4 == 422481 ** 4)
True

It is known that this is the only such quadruple of numbers where all numbers are less than a million. For \(n=5\), the minimal counterexample will have smaller numbers—see the screenshot of one of the shortest scientific articles.

For the curious 🤓

This counterexample can be found by exhaustive search. The code below simply iterates over all quintuplets of numbers \(1 \le a, b, c, d, e < 150\). As soon as the required quintuplet is found, it is printed and the program terminates. 

from itertools import product

for a, b, c, d, e in product(range(1, 150), repeat=5):
    if a ** 5 + b ** 5 + c ** 5 + d ** 5 == e ** 5:
        print(a, b, c, d, e)
        break

This code will run for a long time. It can be sped up, for example, as follows:

  1. If a quintuplet of numbers \(a,b,c,d,e\) satisfies the condition, then the numbers \(a,b,c,d\) can be permuted in any way. To avoid unnecessary iterations, we can agree that \(a \le b \le c \le d\). To iterate over such quadruples, we can use the \(\texttt{combinations}\) generator instead of \(\texttt{product}\).
  2. Precompute an array of fifth powers of numbers from the interval \([1,149]\), and then check whether the sum of any four of its elements lies in this array.

The resulting optimized code will run much faster. 

from itertools import combinations

powers = {i ** 5 for i in range(1, 150)}
print(next(c for c in combinations(powers, 4) if sum(c) in powers))