Making numbers from 2, 0, 1, 7. Also: are the the iterative factorials and square roots, starting from any $s>2$, dense in $[1,\infty)$?

Solution 1:

I'm not sure if it's proper SE etiquette to revive older posts, but this one had me interested. My results were inconclusive but counter-intuitive and intriguing.

There are a lot of interesting questions in this post, but I thought I'd tackle a subset of the problem stated as the Main Question. For clarification, my answer applies to the following question:

For some fixed integer $n \gt 2$, can we generate any positive integer by applying to $n$ a finite number of factorials, then square roots, then a floor function, in that order?

If we follow this order, the final operation is a floor function. Then $m = \lfloor x^{1/2^{k}} \rfloor$ for some $x$ and for some integer $k$ (where $k$ is exactly the number of square roots). By definition of the floor function, this implies $x^{1/2^{k}} \in [m, m+1)$, i.e. $x \in [m^{2^{k}}, (m+1)^{2^{k}})$. We also know $x$ was the result of an arbitrary number of factorials of $n$, so let $x = (...(n!)!...)!$.

From the above we can see that: \begin{align} x &\lt (m+1)^{2^{k}} \\ x &\ge m^{2^{k}} \end{align}

from which we can solve for $k$ in each expression and bound it as well:

$$ \frac{\log\log x - \log\log(m+1)}{\log 2} \lt k \le \frac{\log\log x - \log\log m}{\log 2} $$

This states that if there exists an integer $k$ satisfying the above, we can generate $m$ by applying $k$ square roots and then a floor function. Clearly this is dependent on $x = (...(n!)!...)!$ and $m$, but we can note a couple of things. Call the right bound $f(x, m)$ and the left $g(x,m)$, so that $f(x,m) \gt g(x,m).$

The interval $(g(x,m), f(x,m)]$ can be as tiny as it wants so long as it includes some integer $k$. But if the interval is too small, the probability of finding some such integer should decrease. With this in mind, note that

\begin{align} \lim_{m \to \infty}{f(x,m)-g(x,m)} &= \lim_{m \to \infty}{\frac{\log\log x - \log\log(m+1) - \log\log x + \log\log m}{\log 2}} \\ &= \lim_{m \to \infty}{\frac{\log\log m - \log\log(m+1)}{\log 2}}\\ &= 0 \end{align}

which demonstrates that as we try to generate larger and larger integers $m$, the interval becomes tighter and tighter irrespective of our choice of $n$, and more interestingly, irrespective of the chosen number of factorials.

This proves nothing, since the number of factorials can still influence which interval we land in, but the fact that for large $m$ it becomes harder and harder to find a $k$ satisfying the above inequality seems to imply that this will become impossible as $m$ grows. Even though this result doesn't prove or refute the question statement it still is counter-intuitive to what I expected, hence I'm posting it here.

This answer might be improved by some sort of generalized expression or Sterling approximation to further simplify $\log\log x$ where $x = (...(n!)!...)!$. Something similar to:

$$ \log x! = \log 1 + \log 2 + ... + \log x. $$