# How many fours are needed to represent numbers up to $N$?

The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols.

For example, $165=\left(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}\right) \div .4$.

If we remove the restriction on the number of fours, let $f(N)$ be the number of fours required to be able to represent all positive integers no greater than $N$. What is the asymptotic behaviour of $f(N)$? Can it be shown that $f(N) \sim r \log N$ for some $r$?

To be specific, let’s restrict the operations to the following:

• addition: $x+y$
• subtraction: $x-y$
• multiplication: $x\times y$
• division: $x\div y$
• exponentiation: $y^x$
• roots: $\sqrt[x]{y}$
• square root: $\sqrt{x}$
• factorial $n!$
• decimal point: $.4$
• recurring decimal: $. \overline 4$

It is easy to see that $f(N)$ is $O(\log N)$. For example, with four fours, numbers up to $102$ can be represented (see here for a tool for generating solutions), so, since $96 = 4\times4!$, we can use $6k-2$ fours in the form $(\dots((a_1\times 96+a_2)\times 96+a_3)\dots)\times96+a_k$ to represent every number up to $96^k$.

On the other hand, we can try to count the number of distinct expressions that can be made with $k$ fours. For example, if we (arbitrarily) permit factorial only to be applied to the digit $4$, and allow no more than two successive applications of the square root operation, we get $\frac{216^k}{18}C_{k-1}$ distinct expressions where $C_k$ is the $k$th Catalan number. (Of course, many of these expressions won’t represent a positive integer, many different expressions will represent the same number, and the positive integers generated won’t consist of a contiguous range from $1$ to some $N$.)

Using Stirling’s formula, for large $k$, this is approximately $\frac{864^k}{72k\sqrt{\pi k}}$. So for $f(N)$ to grow slower than $r\log N$, we’d need to remove the restrictions on the use of unary operations. (It is well-known that the use of logs enables any number to be represented with only four fours.)

Can this approach be extended to show that $f(N)$ is $\Omega(\log N)$? Or does unrestricted use of factorial and square roots mean that $f(N)$ is actually $o(\log N)$? Is the answer different if the use of $x\%$ (percentages) is also permitted?

• One more variant might include allowing concatenation (e.g. using $44$ or $444$). – J. M. isn't a mathematician Dec 23 '11 at 18:12
• @PatrickDaSilva, I’ve used \cdot for the decimal point because a central dot is the convention in the U.K. for writing decimals (e.g. $3\!\cdot\!\! 14159$, not $3.14159$). A dot above a digit is created using \dot and is for recurring decimals (e.g. $\frac{1}{3}=0\!\cdot\!\!\dot 3$). I know conventions in other countries differ (e.g. the use of commas for decimal points in some mainland European countries). – David Bevan Dec 23 '11 at 18:26
• By the way, if you allow logarithms, you don't even need four fours: actually three fours are enough to represent any positive integer like $\log\bigl(\log 4/\log(\surd\surd\dots\surd4)\bigr)/\log 4$. – Zsbán Ambrus Mar 4 '12 at 12:02
• To my knowledge this problem is open, and difficult, even for the case of 1s instead of 4s, and allowing only addition and multiplication. – user7530 Dec 24 '12 at 22:49
• I'd prefer to remove the decimal and repeated-decimal operations. A "pure" representation of $N$ by fours shouldn't rely on the accident of the numerical base. – Blue Jan 6 '13 at 10:02

I'm one of the authors of the paper referenced by David Bevan in his comment. The four-fours was one inspiration for that problem, although others have thought about it also. The specific version of the problem there looks at the minimum number of 1s needed to represent n where one is allowed only addition and multiplication but any number of parentheses. Call this g(n). For example, g(6) <= 5, since 6=(1+1)(1+1+1), and it isn't hard to show that g(6)=5. Even in this limited version of the problem, the question is generally difficult even to get asymptotics.

In some sense most natural questions of asymptotic growth are somewhat contained in this question, since one can write any given k as 1+1+1...+1 k times, and 1=k/k. Thus starting with some k other than 1 (such as k=4), the asymptotics stay bounded within a constant factor, assuming that addition and division are allowed.

However, actually calculating this sort of thing for any set of operations is generally difficult. In the case of integer complexity one has a straightforward way of doing so, since if one calculates g(i) for all i less than n, calculating g(n) is then doable. This doesn't apply when one has other operations generally, with division and substraction already making an algorithm difficult. In this case, one can make such an algorithm but exactly how to do so is more subtle. In fact, as long as one is restricted to binary operations this is doable (proof sketch: do what you did to look at all distinct expressions).

Adding in non-binary operations makes everything even tougher. Adding in square roots won't make things that much harder, nor will adding factorial by itself. The pair of them together makes calculating specific values much more difficult. My guess would be that even with factorial, square root and the four binary operations there are numbers which require arbitrarily large numbers of 1s, but I also suspect that this would be extremely difficult to prove. Note that this is already substantially weaker than what you are asking- whether the order of growth is of log n. Here though square roots probably don't alter things at all; in order for it to matter one needs to have a lot numbers of the form n^2^k with surprisingly low complexity. This seems unlikely.

• The series with $1$'s is oeis.org/A005245 I didn't find any asymptotics there or at the easier linked oeis.org/A061373 but that one shows that the question is $O(\log N)$ as here for m=2^p3^q, a(m)=2p+3q – Ross Millikan Feb 26 '13 at 3:09
• For the case of just + and *, the growth is known to be of O(log n) as the correct level. This and related details are discussed in the paper that Bevan referenced. Whether it is asymptotic to c log n for some constant c is open. – JoshuaZ Feb 26 '13 at 3:18
• @user7530 Er, sorry, when I wrote f(n) I meant to define g(n). I had written it with f(n), then realized that using the same letter as the OP wasn't a good idea. I tried to go and make them all consistent but missed a few. Should be ok now. – JoshuaZ Feb 26 '13 at 4:04

You can get $$103$$ with five $$4$$s as $$\frac {\sqrt{\sqrt{\sqrt{4^{4!}}}}+4+\sqrt{.\overline4}}{\sqrt{.\overline4}}=103$$

For four $$4$$s, we have $$\dfrac {44}{.\overline 4}+4=103$$.

In fact, $$113$$ is the first number I can't get with four $$4$$s.

• In reply to not knowing how to get the math notation: You can search for LaTeX tutorials and get most of the notation right there; it also doesn't hurt to click on "edit" in other people's posts just to see how they are doing it (you don't actually have to edit anything). – Dennis Meng Oct 20 '13 at 3:25
• (And welcome to the site!) – Dennis Meng Oct 20 '13 at 3:26
• Thanks! Incidentally, my example actually needs five 4s, but I know I've done it with four. – Mark Stephenson Oct 20 '13 at 23:42
• 103 = 44 / .4. + 4 – David Bevan Oct 21 '13 at 9:59
• Ah, mea culpa, most results of cut-the-knot.org/arithmetic/funny/4_4.shtml are not applicable because it often uses the floor function. But they give 114 = 44/.4 + 4. Sadly, @Eliseod'Annunzio solution for 113 isn't applicable because % isn't explicitely allowed as well. – Cœur Sep 30 '18 at 20:18

Go here to look at a YouTube video discussing the matter. It proves that for all $n\in\mathbb{Z}^+$, $$\LARGE\log_{\frac 12}(\log_4\sqrt [n]{4}) = n.$$ But notice that $\dfrac 12 = \dfrac 24 = \dfrac{\sqrt{4}}{{4}}$ so...

Edit: By $n^\text{th}$ root, I mean $n$ square roots. So for example, $\sqrt  {4} = \sqrt{\sqrt{4}}$ (because it is simple to write it this way).

• It was already aknowledge in the question itself that log was enabling any number to be represented with only four fours. – Cœur Sep 30 '18 at 20:28
• @Cœur where, exactly? Is that expressed in the big-$O$ notation? I ain't familiar with that. – Mr Pie Sep 30 '18 at 20:46
• Last sentence before the final quote: "(It is well-known that the use of logs enables any number to be represented with only four fours.)" – Cœur Sep 30 '18 at 20:56

It can't be $o(\log N)$ for any finite set of binary operations. For a set of operations of size $k$, you can only have of order $k^N$ legal strings, so you can't represent more numbers than that.

• Not all of the operations are binary. For example, $$4!!!!\cdots !!!$$ for any number of factorials, can be written with one four – Zubin Mukerjee Jan 11 '15 at 16:50