215
$\begingroup$

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?

  • 4
    One more variant might include allowing concatenation (e.g. using $44$ or $444$).2011-12-23
  • 1
    Why did you use \cdot for the decimal point? It puts dots over your numbers ; it's just plain weird. You should just put a single dot, like this ".".2011-12-23
  • 3
    @Patrick, I think the dots over the digits indicate repeating decimals.2011-12-23
  • 13
    @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).2011-12-23
  • 1
    @David : Sorry then, it's just that it confused me at first since I've never seen dots above things except for derivatives wrt time in physics. Thanks for clarifying.2011-12-23
  • 63
    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 $.2012-03-04
  • 3
    This seems to be related to the concept "integer complexity". For example, see the recent paper by Harry Altman and Joshua Zelinsky, "Numbers With Integer Complexity Close to the Lower Bound" in [INTEGERS: The Electronic Journal of Combinatorial Number Theory](http://integers-ejcnt.org/vol12a.html).2012-10-19
  • 5
    To my knowledge this problem is open, and difficult, even for the case of 1s instead of 4s, and allowing only addition and multiplication.2012-12-24
  • 1
    I wonder if it can be proved that one $4$ is sufficient to represent all positive integers if a floor function is also allowed?2013-01-06
  • 5
    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.2013-01-06
  • 2
    I can see the simplicity of the problem as posed in @DavidBevan link "Numbers With Integer Complexity Close to the Lower Bound", but with increasing the number of operations allowed the problem becomes rather arbitrary. Can someone explain the significance of the problem?2013-01-12
  • 0
    You should make the second half of your question an answer. [You *are* allowed to answer your own questions.](http://blog.stackoverflow.com/2011/07/its-ok-to-ask-and-answer-your-own-questions/)2013-02-15
  • 2
    Let's see which method is [Fourier](http://www.neatorama.com/2013/02/03/Higher-Math/).2013-02-26
  • 0
    @ZsbánAmbrus Can you please explain?2016-05-19
  • 0
    Note that using [`floor` (or `ceiling`) also enables any integer to be represented with just one four](https://math.stackexchange.com/questions/48633/using-floor-ceiling-square-root-and-factorial-functions-to-get-integers), and using [`sec(atan())` also enables any integer to be represented with just one four](http://paulbourke.net/fun/4444/jim_millar.html). @DanBrumleve2018-09-30

4 Answers 4