So, several days ago, I was introduced to the "Four game" again. The object of the game is to use four 4's to produce as many integers as you can. You are allowed to use addition, subtraction, multiplication, division, square root, and factorial functions in addition to concatenation (44), use of a decimal point (.4), and possibly the floor and ceiling functions. With these abilities, one can get all integers between 1 and 156 and my friends and I are not even done yet. What is particularly helpful is being able to define a large range of integers with just one four and the single-input functions. For instance…
$1 = \lceil .4 \rceil$
$2 = \sqrt{4}$
$3 = \left\lceil \sqrt{\sqrt{4!}} \;\;\right\rceil$
$4 = 4$
$5 = \left\lceil \sqrt{4!} \right\rceil$
$6 = \left\lceil \sqrt{\sqrt{4!}} \;\;\right\rceil!$
$7 = \left\lceil \displaystyle\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{ \left\lfloor \sqrt{ \;\;\left\lfloor \sqrt{\sqrt{ \left\lceil \sqrt{4!} \right\rceil ! }} \right\rfloor !!\;\; } \right\rfloor ! }}}}} \;\;\right\rceil$
More legibly, though less impressively, set
$$T=\sqrt{ \left\lceil \sqrt{4!} \right\rceil ! }\qquad S=\sqrt{ \;\left\lfloor \sqrt{T\; } \right\rfloor !!}\qquad R=\sqrt{\sqrt{\sqrt{ \left\lfloor S \right\rfloor ! }}}\qquad;$$
then $7=\left\lceil \displaystyle\sqrt{\sqrt{R}} \;\;\right\rceil$.
$8 = \left\lfloor \sqrt{\sqrt{ 7! }} \right\rfloor$
$9 = \left\lceil \sqrt{\sqrt{ 7! }} \;\;\right\rceil$
$10 = \left\lfloor \sqrt{ \left\lceil \sqrt{ 4!} \right\rceil ! } \right\rfloor$
$11 = \left\lceil \sqrt{ \left\lceil \sqrt{ 4!} \right\rceil ! } \right\rceil$
…
I haven't looked for one for 12 yet, but I doubt it would be hard to find it. Thus, my question is:
Is it possible to express every integer using only a single four and any number of floor, ceiling, square root, and factorial functions?
Best Answer
I've numerically verified that this is possible for all numbers up to 208. Here's a heuristic argument why we can expect it to be possible for all numbers:
After the last factorial, the remaining operations are floors, ceilings and square roots. The natural number $n$ is reachable from a number $m$ using these operations iff $(n-1)^{2^k}<m<(n+1)^{2^k}$ for some $k\in\mathbb N_0$: If this condition is fulfilled, we can draw $k$ square roots and then take either the floor or the ceiling to reach $n$; if it isn't fulfilled, then taking the floor or ceiling in between drawing square roots won't help, since it will never cause the value to cross the boundaries $(n\pm1)^{2^k}$. (Note that the expressions for $n$ up to $11$ reflect this; the floor or ceiling operations are never directly followed by a square root.)
Taking logarithms, we have that $n$ is reachable from $m$ iff $2^k\ln(n-1)<\ln m<2^k\ln(n+1)$. If we consider the logarithm of $m$ to be "randomly" distributed, we can ask for the "probability" of a factorial fulfilling this condition. The length of the admissible interval is $2^k(\ln(n+1)-\ln(n-1))$, and this has to be put in relation to the distance between successive intervals, which is $2^{k+1}\ln n-2^k\ln n=2^k\ln n$. (This is the distance to the next higher interval; the distance to the next lower interval is $2^{k-1}\ln n$, but the difference isn't relevant in what follows.)
Thus, the proportion of values fulfilling the condition is $2^k(\ln(n+1)-\ln(n-1))/(2^k\ln n)=(\ln(n+1)-\ln(n-1))/\ln n$. The exact value isn't important; the key point is that this is independent of $k$ and thus doesn't decrease as $m$ increases. Thus, for each $m$, the "probability" of $m$ fulfilling the condition is roughly the same, as long as it makes sense to regard the logarithm of $m$ as uniformly distributed. But we know that infinitely many values of $m$ are reachable, namely at the very least the ones we get by repeatedly taking factorials, starting with $4$, and it's plausible that there is no systematic relationship between these values and the above intervals, so that the logarithms of these values of $m$ can be regarded as uniformly distributed. Since for any given $n$ each of these values of $m$ has the same finite probability of $n$ being reachable from it, we can expect to eventually find some $m$ from which $n$ is reachable.