# Solution: x! + y! + z! = x * y * z

Last time I discussed the fact that there is a single, unique, solution to the formula x ! + y ! + z ! = x * y * z, where x, y, and z are non-negative integers.  I asked for a computer program to find the solution given that x, y, and z are all <= 9 but I wondered aloud whether the solution was unique without that constraint.

The part where a computer can’t help is the uniqueness.  Here is a mathematical proof that there are no solutions if any of x, y, or z are >= 6:

Assume without loss of generality that x >= y => z.  The following two inequalities hold trivially, since we’re dealing with non-negative numbers:

x ! + y ! + z ! > x !
x * y * z <= x 3

Here’s where 6 comes in:

Lemma: for x >= 6, x ! > x 3 (proof momentarily.)

If this lemma were true, then we’d be done… for x >= 6,

x ! + y ! + z ! > x ! > x 3 >= x * y * z

So a search for solutions for x ! + y ! + z ! = x * y * z can be restricted to 5 >= x >= y >= z.  This is computationally feasible.
By inspection, there is a unique solution (see later in this post.)

Proof of lemma: first, look at values of x ! and x 3 for x = 0 through 7:

0! = 1 > 0 = 03
1! = 1 = 1 = 13
2! = 2 < 8 = 23
3! = 6 < 27 = 33
4! = 24 < 64 = 43
5! = 120 < 125 = 53
6! = 720 > 216 = 63
7! = 5040 > 343 = 73

It’s not immediately clear how to progress.  The key idea, as often in geometric-ish progressions: look at successive ratios.  The initial 0 messes things up a bit, so we’ll start with x = 1.

On the left, numbers advance by a factor of:

(x + 1)! / x ! = x + 1

Note this ratio gets bigger and bigger.

On the right, numbers advance by a factor of

(x + 1)3 / x 3 = ((x + 1) / x)3 = (1 + (1 / x))3

Note this rate of increase actually gets smaller.

The crossover point – where x ! stops losing ground and begins to catch up – is x = 3;

1 + 1 = 2 < 8 = (1 + (1/1))3
2 + 1 = 3 < 3.375 = (1 + (1/2))3
3 + 1 = 4 > 2.370370… = (1 + (1/3))3

By x = 6, the lost ground has been made up, and x ! never looks back. QED.

By the proof above, it only remains to look at the finite number of cases where x, y, and z are all <= 5.  Here they all are: note that in addition to the unique solution for the equality

x ! + y ! + z ! = x * y * z

there are only four solutions to the inequality

x ! + y ! + z ! < x * y * z

All of the other cases have

x ! + y ! + z ! > x * y * z.

 0! + 0! + 0! = 3 > 0 = 0 * 0 * 0 1! + 0! + 0! = 3 > 0 = 1 * 0 * 0 1! + 1! + 0! = 3 > 0 = 1 * 1 * 0 1! + 1! + 1! = 3 > 1 = 1 * 1 * 1 2! + 0! + 0! = 4 > 0 = 2 * 0 * 0 2! + 1! + 0! = 4 > 0 = 2 * 1 * 0 2! + 1! + 1! = 4 > 2 = 2 * 1 * 1 2! + 2! + 0! = 5 > 0 = 2 * 2 * 0 2! + 2! + 1! = 5 > 4 = 2 * 2 * 1 2! + 2! + 2! = 6 < 8 = 2 * 2 * 2 3! + 0! + 0! = 8 > 0 = 3 * 0 * 0 3! + 1! + 0! = 8 > 0 = 3 * 1 * 0 3! + 1! + 1! = 8 > 3 = 3 * 1 * 1 3! + 2! + 0! = 9 > 0 = 3 * 2 * 0 3! + 2! + 1! = 9 > 6 = 3 * 2 * 1 3! + 2! + 2! = 10 < 12 = 3 * 2 * 2 3! + 3! + 0! = 13 > 0 = 3 * 3 * 0 3! + 3! + 1! = 13 > 9 = 3 * 3 * 1 3! + 3! + 2! = 14 < 18 = 3 * 3 * 2 3! + 3! + 3! = 18 < 27 = 3 * 3 * 3 4! + 0! + 0! = 26 > 0 = 4 * 0 * 0 4! + 1! + 0! = 26 > 0 = 4 * 1 * 0 4! + 1! + 1! = 26 > 4 = 4 * 1 * 1 4! + 2! + 0! = 27 > 0 = 4 * 2 * 0 4! + 2! + 1! = 27 > 8 = 4 * 2 * 1 4! + 2! + 2! = 28 > 16 = 4 * 2 * 2 4! + 3! + 0! = 31 > 0 = 4 * 3 * 0 4! + 3! + 1! = 31 > 12 = 4 * 3 * 1 4! + 3! + 2! = 32 > 24 = 4 * 3 * 2 4! + 3! + 3! = 36 = 36 = 4 * 3 * 3 4! + 4! + 0! = 49 > 0 = 4 * 4 * 0 4! + 4! + 1! = 49 > 16 = 4 * 4 * 1 4! + 4! + 2! = 50 > 32 = 4 * 4 * 2 4! + 4! + 3! = 54 > 48 = 4 * 4 * 3 4! + 4! + 4! = 72 > 64 = 4 * 4 * 4 5! + 0! + 0! = 122 > 0 = 5 * 0 * 0 5! + 1! + 0! = 122 > 0 = 5 * 1 * 0 5! + 1! + 1! = 122 > 5 = 5 * 1 * 1 5! + 2! + 0! = 123 > 0 = 5 * 2 * 0 5! + 2! + 1! = 123 > 10 = 5 * 2 * 1 5! + 2! + 2! = 124 > 20 = 5 * 2 * 2 5! + 3! + 0! = 127 > 0 = 5 * 3 * 0 5! + 3! + 1! = 127 > 15 = 5 * 3 * 1 5! + 3! + 2! = 128 > 30 = 5 * 3 * 2 5! + 3! + 3! = 132 > 45 = 5 * 3 * 3 5! + 4! + 0! = 145 > 0 = 5 * 4 * 0 5! + 4! + 1! = 145 > 20 = 5 * 4 * 1 5! + 4! + 2! = 146 > 40 = 5 * 4 * 2 5! + 4! + 3! = 150 > 60 = 5 * 4 * 3 5! + 4! + 4! = 168 > 80 = 5 * 4 * 4 5! + 5! + 0! = 241 > 0 = 5 * 5 * 0 5! + 5! + 1! = 241 > 25 = 5 * 5 * 1 5! + 5! + 2! = 242 > 50 = 5 * 5 * 2 5! + 5! + 3! = 246 > 75 = 5 * 5 * 3 5! + 5! + 4! = 264 > 100 = 5 * 5 * 4 5! + 5! + 5! = 360 > 125 = 5 * 5 * 5

Here’s the program I used to check the cases for x, y, z <= 9.  I used perl.  Note the similarity to Zbyszek’s solution (link removed because the comment did not survive the blog migration.)

proof.pl on GitHub

A cute little exercise.

EDIT 2020-10-22: moved proof script to GitHub