# Using floor, ceiling, square root, and factorial functions to get integers

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?

-
I would look for an inductive proof: if $1,2,3,...,n$ are expressible, then $n+1$ should be. – Beni Bogosel Jun 30 '11 at 9:32
You can do it with trig functions - paulbourke.net/fun/4444/jim_millar.html – user1729 Jun 30 '11 at 10:19
@Beni: And we should probably try and prove the statement that if we allow a single number (instead of just four) from $1,2, \dots n$ ($n \gt 4$), then we can express $n+1$. – Aryabhata Jun 30 '11 at 15:50
@Aryabhata: Yes, that should do it. There is another idea. If we could prove that if $n$ is expressible in that form, then $n-1$ is expressible. Since we can construct a sequence $(k_n)\to \infty$ of expressible numbers, this would also complete the proof. Anyway, I don't have any ideas as to HOW could we do that. – Beni Bogosel Jun 30 '11 at 15:57

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.

-
Another way to say the same thing is that (starting with $2^k\lg(n-1) < \lg m < 2^k\lg(n+1)$ where $\lg$ is logarithm to base 2) we want that, for some integer $k$, $k + \lg\lg(n-1) < \lg\lg m < k + \lg\lg(n+1)$, i.e., the fractional part of $\lg\lg m$ lies between the fractional part of $\lg\lg(n-1)$ and that of $\lg\lg(n+1)$, where $m$ is a factorial. This seems a lot like inhomogeneous diophantine approximation, and we'd suspect something similar is true (the fractional part of $m!$ is equidistributed or at least dense in [0,1]). – ShreevatsaR Jul 1 '11 at 6:19
In fact, whether that last part is true is a question of independent interest IMHO, so I've asked it as a new question here. – ShreevatsaR Jul 1 '11 at 6:35
@ShreevatsaR: Yes, that's a good way of putting it. But note that $m$ can't be just any factorial; it has to be the factorial of a number which is itself reachable. – joriki Jul 1 '11 at 9:08
Oh, another thing I missed. So even the fact that $\{\log\log r!\}$ is dense in $[0,1]$ (which is shown easily by Andrew in the linked question) is not strictly enough to complete the proof here entirely… but it's strong evidence I guess. – ShreevatsaR Jul 1 '11 at 17:25