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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s