ARPAVAX:reeds (08/22/82)
Four 4's problem: Hard for udergraduates, sure. And hard for us because it is not a very well specified problem. Here are three solutions and an open problem: 1. If you are allowed arbitrarily many copies of the arithmetic operators: * / + - ** (ie, multiply, divide, add, subtract, power), arbitrarily many parentheses for grouping, and only four 4s, and no other math symbols, you cannot express all integers: there are only finitely many different expression trees you can build. 2. If you are also allowed arbitrarily many copies of the symbol pi you can easily build all integers. For instance, 5 can be expressed as (pi+pi+pi+pi+pi)/pi + 4 + 4 -4 -4 and so on. 3. If you are allowed all of the stuff in 1 and arbitrarily many applications of the functions sqrt() and log(), you can express any positive integer: 3a. With one 4 you can express any number of the form 4**(2**-n) for integer n by taking successive square roots: sqrt(4) = 4 **(1/2) sqrt(sqrt(4)) = 4 ** (1/4) sqrt(sqrt(sqrt(4))) = 4 ** (1/8) and so on. 3b. Now take logs twice: log ( log ( sqrt (... (sqrt(4)...) ) ) = log ( log ( 4 **(2**-n))) = log(2**(-n)*log(4)) = -n *log(2) + log(log(4)) 3c. So do this twice, once with n = k+1 and once with n = 1, at the cost of two 4s. Subtract the two expressions to get log(log(sqrt(sqrt(...4)))) - log(log(sqrt(4))) = -(k+1)*log(2) + log(log(4)) + 1*log(2) - log(log(4)) = k * log(2) 3d. Now do this again, at the cost of the other two 4s, with j instead of k. Take the ratio of the two results, and you get k*log(2) / (j * log(2)) = k/j This is how you can represent any positive rational by using four 4s. This clearly includes all positive integers. These 3 cases are instructive: too strict an interpretation of the problem and it clearly cannot be done. Slight loosenings of the problem and it is trivial. Is there any half-way place, where it cannot be so easilly solved? Here is a conjecture: Let f(x) = sqrt(x) be the square-root function, and let g(x) = exp(x) be the exponential function. Let t be any fixed real number bigger than 1. Consider the image of t under the repeated promiscuous application of f and g: that is, the set of all numbers like f(f(g(f(g(g(f(t))))))) and so on. Call the set of such numbers the "funny set". This set is conjectured to be dense in the set of reals greater than 1. I mean, any real number bigger than 1 can be approximated as closely as you like by numbers in the funny set. If this is true then there is another way to make all integers with four 4s and arbitrarily many applications of f(x), g(x) and with the greatest- integer function [x]: use t = 4+4+4+4, say. To represent the integer n, approximate n+.5 with a number in the funny set. Then round the funny number down with [x]. More interesting: what pairs of functions f and g have that property? [I suspect that just about any pair of functions does, provided that they do not commute (f(g(x)) != g(f(x)) and one of them grows slower than x and one grows faster than x.] Any ideas on this?