18
$\begingroup$

My daughter (10 years old) was given the task by her math teacher to form as many numbers as she could using the numbers: 2, 0, 1, 7, exactly once each, and the operations of addition, subtraction, multiplication, division, exponents, and factorial, with free use of parentheses. (It was not allowed to combine the numbers directly as digits, like $21$, but you can make $21$ as $7\cdot(2+1)+0$.)

For example,

$0 = 0\cdot 2^{(7+1)!!}$

$1 = 2-1+0\cdot 7$

$2 = 2+0\cdot(7+1)$

$3 = 2+1+0\cdot 7$

and so on. She went a long way, and made a lot of numbers. But there was a gap in her list: she's couldn't make 19.

Question. Can you make 19? Or, how can we prove that this is impossible?

I suggested to her that we simply enlarge the list of allowed operations, since I knew that she knew already about the square-root function $\sqrt{\ }$. In order to stay within the integers, I suggested that we also allow the floor and ceiling functions, which I taught her.

Before too long, working with pencil on paper (but asking me "what is the square root of $720$?"), she had noticed that $3!!=6!=720$ and $\sqrt{720}\approx 26.83$, and consequently $$19=\text{floor}\Big(\sqrt{(2+1+0)!!}-7\Big).$$

She was mighty pleased to have solved the problem while I was still trying unsuccessfully to do so.

Meanwhile, I was thinking that having added square-root and floor might have made our set of operations very powerful.

Main question. Can one represent any positive integer by an expression using factorials, square-roots and the floor function, starting from the number $7$?

Indeed, I had in mind that one could make any desired number simply by iterating the factorial an enormous number of times, and then iteratively taking the square-root an enormous number of times, choosing those two numbers so as to balance each other in such a way that one comes very close to the desired number, with the floor function at the end polishing it off.

I made a Google+ post about it, and Timothy Gowers commented, speculating that perhaps such a thing might happen "by chance" with high probability, and perhaps that idea can be turned into a proof.

What I suspect is true is the following:

Conjecture. For any integer $s>2$, the collection of real numbers obtained by iterating the factorial function on $s$ an arbitrary finite number of times, and then iteratively taking the square root a number of times, is dense in the real interval $[1,\infty)$.

Can you prove or refute it?

See the related questions, which have some overlap with this question:

But there seems to be no answer there.

$\endgroup$
8
$\begingroup$

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. $$

$\endgroup$
  • 3
    $\begingroup$ Welcome to Math SE, it is definitely proper etiquette to provide such nice input to any question, be it old ones or new ones. Cheers! $\endgroup$ – user409521 Mar 20 '17 at 1:01
  • 1
    $\begingroup$ I count it as progress, thanks very much! $\endgroup$ – JDH Mar 20 '17 at 1:01
  • 1
    $\begingroup$ @Phyllotactic thank you! JDH of course, it's a fun problem. $\endgroup$ – Junkhook9000 Mar 20 '17 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.