4. The 4 Fours Problem

The following problem was sent to the MathGroup email list in June 2002.

Q: Find the numbers 0 to 99 using any rational operator (i.e., an operation which results in a rational number) and 4 fours, where each equation must contain no more and no less than 4 fours. Not all numbers may be possible. Some examples include:



.

The problem as formulated is rather unclear because of the vagueness of the phrase "rational operator." The question allowed not only binary operations but also unary operations, such as taking the square root or factorials. This of course means that there is an infinite number of possible solutions unless one imposes additional restrictions. However, we shall first simplify the problem and consider only binary operations: addition, subtraction, multiplication, division, and exponentiation. Let us try to solve the following simpler version of the problem.

Q: Find all integers between 1 and 99 that are expressible using 4 fours and only the arithmetical operations: +, -, *, /, and ^.

This is very easy to implement in Mathematica using algebraic programming. In fact, we shall use exactly the same method as in the last example.

The idea is very simple. First we find all ways of writing expressions like , where the are the binary operations Times, Plus, Divide, Subtract, and Power. Actually in Mathematica, Times and Plus are n-ary operations for any , but Divide, Subtract, and Power are not. To handle them all simultaneously, we consider them to be binary operations.

It is clear that the number of different expressions that can be made up of four arguments and binary operations (which may be different or the same) can be described as follows. Let be an associative binary operation. Then expressions such as and are equal. Clearly the number of such expressions that are equal by virtue of the associativity of (which we found in the previous section) is equal to the number of distinct ways of applying three binary functions to four arguments. In fact we can obtain all the expressions of the latter type from those of the former as follows.

First we repeat what we did above, that is, define an associative operation f.

Next, just as above, we find all the ways of "associating" four elements.

Then we remove all duplicates and expressions that involve the application of g to three elements.

Finally we replace g by , in this order, and make all the elements equal to 4.

(A different approach to the same problem can be found in exercise 13 of Chapter 6 of [2].)

We shall now simply substitute the five binary operations Plus, Subtract, Times, Divide, and Power for in all possible ways. First we need to redefine Divide and Power. Basically we do this to avoid error messages caused by division by 0. For later use, we also place a restriction on the maximum and minimum size of the exponent to avoid unnecessary computations of very large and very small numbers.

Next we create a set of rules that we shall use to create all possible ways of replacing the with the binary operations.

Here is what the list we created looks like.

In fact, since an actual formula never involves more than three binary operations, we remove the rules involving unnecessary s.

Let us now find all possible solutions of the "easy" 4 fours problem.

Finally let us find all possible ways of obtaining a given number, for example, 7.

This completely solves the "easy" 4 fours problem. We can solve the analogous 5 fives problem and so on in exactly the same way. In the final section we take a look at the "hard" 4 fours problem presented in the original question.