[1] A similar problem involving arranging four identical digits to equal a certain amount was given in Thomas Dilworth's popular 1734 textbook The Schoolmaster's Assistant, Being a Compendium of Arithmetic Both Practical and Theoretical.
[2] W. W. Rouse Ball described it in the 6th edition (1914) of his Mathematical Recreations and Essays.
Other operations allowed by some variations include the reciprocal function ("1/x"), subfactorial ("!"
A common use of the overline in this problem is for this value: Typically, the successor function is not allowed since any integer above 4 is trivially reachable with it.
This works by noticing three things: Writing repeated square root in this form we can isolate n, which is the number of square roots: We can isolate both exponents by using the base 4 logarithm: This logarithm can be thought of as the answer to the question: "4 to what power gives me 4 to the half power to the n power?"
so we are now left with: and now we can take a logarithm to isolate the exponent, n: so, putting it all together: Now, we can rewrite the base (1/2) with only 4s and the exponent (1/2) back to a square root: We have used four fours and now the number of square roots we add equals whatever non-negative integer we wanted.
Additionally, solutions that repeat operators are marked in italics.
Others simply prefer "interesting" solutions, i.e., a surprising way to reach the goal.
represent the 14th and 127th multifactorials respectively and should technically be denoted with that many exclamation marks to adhere to the rules of the problem.
Note that the number 113/16 can be written by three 4's, but this does not help for 113 unless the square function (i.e. sq(4) = 16) is allowed.
The use of percent ("%") admits solutions for a much greater proportion of numbers; for example, 113 = (√4 + (√4 + 4!
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.
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) and (for n=2).
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.
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 more compact formula (in the sense of number of characters in the corresponding value) was chosen every time a key occurred more than once.
In the table below, the notation .6... represents the value 6/9 or 2/3 (recurring decimal 6).