Four Fours - Algorithmics of The Problem

Algorithmics of The Problem

This problem and its generalizations (like the five fives and the six sixes problem, both shown below) may be solved by a simple algorithm. The basic ingredients are hash tables that map rationals to strings. In these tables, the keys are the numbers being represented by some admissible combination of operators and the chosen digit d, e.g. four, and the values are strings that contain the actual formula. There is one table for each number n of occurrences of d. For example, when d=4, the hash table for two occurrences of d would contain the key-value pair 8 and 4+4, and the one for three occurrences, the key-value pair 2 and (4+4)/4 (strings shown in bold).

The task is then reduced to recursively computing these hash tables for increasing n, starting from n=1 and continuing up to e.g. n=4. The tables for n=1 and n=2 are special, because they contain primitive entries that are not the combination of other, smaller formulas, and hence they must be initialized properly, like so (for n=1)

T := "4"; T := ".4"; T := ".4...";

and

T := "44";.

(for n=2). Now there are two ways in which new entries may arise, either as a combination of existing ones through a binary operator, or by applying the factorial or square root operators (which does not use additional instances of d). The first case is treated by iterating over all pairs of subexpressions that use a total of n instances of d. For example, when n=4, we would check pairs (a,b) with a containing one instance of d and b three, and with a containing two instances of d and b two as well. We would then enter a+b, a-b, b-a, a*b, a/b, b/a) into the hash table, including parenthesis, for n=4. Here the sets A and B that contain a and b are calculated recursively, with n=1 and n=2 being the base case. Memoization is used to ensure that every hash table is only computed once.

The second case (factorials and roots) is treated with the help of an auxiliary function, which is invoked every time a value v is recorded. This function computes nested factorials and roots of v up to some maximum depth, restricted to rationals.

The last phase of the algorithm consists in iterating over the keys of the table for the desired value of n and extracting and sorting those keys that are integers. This algorithm was used to calculate the five fives and six sixes examples shown below. The more compact formula (in the sense of number of characters in the corresponding value) was chosen every time a key occurred more than once.