Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) \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?

share|improve this question
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
58  
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
17  
Clearly a question with $50$ votes, $14$ favorites and over $1,500$ views has not received enough attention... –  Asaf Karagila Aug 28 '12 at 17:05
4  
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
4  
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
show 9 more comments

3 Answers

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.

share|improve this answer
    
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
add comment

You can get 103 with four 4s as (64 + 4 + sqrt(.4.))÷sqrt(.4.) where 64 = sqrt(sqrt(sqrt(4^4!))) and .4. = .4recurring = 4/9.

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

[Apologies: this is my first ever post: haven't figured out how to get the math notation.]

share|improve this answer
    
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
    
I took up the Four 4's challenge ages ago... I seem to remember an answer for 113... $$\frac{4}{4\%}+\sqrt{\frac{4}{.\overline{4}}}$$ Taking advantage of the fact that 4% = 0.04 –  Eliseo d'Annunzio Jan 9 at 2:08
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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