TAOCP 5 Exercise 18

We are searching for positive integers \(u,v,w,x,y,z\) satisfying \[ u^6 + v^6 + w^6 + x^6 + y^6 = z^6 \qquad\text{(Euler's conjecture for }n=6\text{)}.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5: Introduction to Sorting

Exercise 18. [M25] (E. T. Parker.) Leonhard Euler once conjectured [Nova Acta Acad. Sci. Petropolitanae 13 (1795), 45–63, §3; written in 1778] that there are no solutions to the equation

$$u^5 + v^5 + w^5 + x^5 + y^5 = z^5$$

in positive integers $u$, $v$, $w$, $x$, $y$, $z$. At the same time he conjectured that

$$x_1^n + \cdots + x_{n-1}^n = x_n^n$$

would have no positive integer solutions, for all $n \ge 3$, but this more general conjecture was disproved by the computer-discovered identity $27^5 + 84^5 + 110^5 + 133^5 = 144^5$; see L. J. Lander, T. R. Parkin, and J. L. Selfridge, Math. Comp. 21 (1967), 446–459.

Infinitely many counterexamples when $n = 4$ were subsequently found by Noam Elkies [Math. Comp. 51 (1988), 825–835]. Can you think of a way in which sorting would help in the search for counterexamples to Euler's conjecture when $n = 6$?

Verified: yes
Solve time: 9m07s

Solution

We are searching for positive integers (u,v,w,x,y,z) satisfying [ u^6 + v^6 + w^6 + x^6 + y^6 = z^6 \qquad\text{(Euler's conjecture for }n=6\text{)}. ] A naive exhaustive search over all (1 \le u,v,w,x,y,z \le M) would require (O(M^5)) time, which is impractical for even moderately large (M). The key idea is to split the five terms on the left into a group of three and a group of two, then use sorting to efficiently find matches between the two groups.

Meet‑in‑the‑middle with sorting

Fix an upper bound (M). Construct two lists:

  • List (L): all sums of three sixth powers [ L = {, a^6 + b^6 + c^6 \mid 1 \le a \le b \le c \le M ,}. ] (The condition (a \le b \le c) avoids permutations of the same sum; it is not strictly necessary but reduces the list size by a constant factor.)

  • List (R): all positive values of the form (z^6 - d^6 - e^6) [ R = {, z^6 - d^6 - e^6 \mid 1 \le d \le e < z \le M,; z^6 > d^6 + e^6 ,}. ]

Both lists have size (O(M^3)). Any solution to the original equation corresponds to a value that belongs to both (L) and (R), because [ u^6+v^6+w^6 = z^6 - x^6 - y^6. ]

Algorithm

  1. Generate all elements of (L) and (R).
  2. Sort (L) and (R) using an (O(N\log N)) sorting algorithm (e.g., merge sort).
  3. Merge the two sorted lists to find every value that appears in both. For each common value (v), we have (a^6+b^6+c^6 = v = z^6-d^6-e^6), which immediately yields a solution ((a,b,c,d,e,z)).
  4. Output the solutions found.

Complexity

Generating each list takes (O(M^3)) time. Sorting takes (O(M^3\log M)) time. Merging takes (O(M^3)) time. The overall time is therefore (O(M^3\log M)), a dramatic improvement over (O(M^5)). The space required is (O(M^3)) for the lists.

Correctness

If ((u,v,w,x,y,z)) is a solution with all variables (\le M), then (u^6+v^6+w^6 \in L) and (z^6-x^6-y^6 \in R), and these two values are equal; hence the merge will find this common value and report the solution. Conversely, any common value found during the merge gives a decomposition (a^6+b^6+c^6 = z^6-d^6-e^6) with all variables in the prescribed ranges, which is exactly a solution to the original equation.

This method,generating two large sets of sums, sorting them, and then merging,is the standard technique for finding counterexamples to Euler’s sum‑of‑powers conjecture. It was used, for instance, by Lander, Parkin, and Selfridge to discover (27^5+84^5+110^5+133^5=144^5) (the case (n=5)). For (n=6) the same approach applies with sixth powers.

This completes the proof. ∎