# Intuition for iterated function for log log log n.

Intuitively, $\log n$ (base 2) is the number of times you have to divide $n$ by 2 before reaching a number around 2. (Waving our hands a little to gloss over floor vs ceiling and $\pm$ 1 errors.) Similarly, $\log \log n$ is the number of times we have to iterate the square root function to get from $n$ down to a number around $2$ (waving our hands again).

What is the intuition for $\log \log \log n$? What is the function that you would iterate $\log \log \log n$ times to get from $n$ down to a small constant?

-
Please explain iterate the square root function...and please wave your hands, only if really needed. – draks ... Jul 27 '12 at 22:19
@draks: Consider the sequence $n, \sqrt n, \sqrt{\sqrt n}, \sqrt{\sqrt{\sqrt n}} \ldots$ – Rahul Jul 27 '12 at 22:20
A deleted comment read: "According to a joke in analytic number theory, $\log\log\log x<4$ for all $x$." – anon Jul 27 '12 at 22:31
@anon, glad you caught it ;) – Bruno Joyal Jul 27 '12 at 22:32
This is not directly relevant to the question, but Joe will probably be interested to learn about the iterated logarithm function, which counts the number of times one must take the logarithm of its argument before the result is less than or equal to 1. – MJD Jul 28 '12 at 2:34

For $\log$, you have $n \mapsto n/2$, which is really $n\mapsto\exp(\log n - 1)$, where $\exp$ is exponentiation with base $2$, i.e. $n\mapsto 2^n$ :-)

For $\log\circ\log$, you have $n\mapsto\sqrt n=\exp\big(\!\frac{\log n}2\!\big)=\exp\exp(\log\log n - 1)$.

So for $\log\circ\log\circ\log$, you'll have $n\mapsto\exp\exp\exp(\log\log\log n - 1)$, which simplifies to... $$n\mapsto2^\sqrt{\log_2 n}.$$ Not very pretty, I'm afraid.

Edit: In retrospect, it's kind of obvious that if you want an iteration that takes about $f(n)$ steps to reach some value, then all you need to do is decrease $f(n)$ by a fixed amount per iteration. So if the iterated function is $n \mapsto m$, you can choose $f(m) = f(n)-1$, so $m = f^{-1}(f(n)-1)$. For example, it should take about $\sqrt n$ iterations of $n\mapsto(\sqrt n-1)^2=n-2\sqrt n+1$ to map $n$ to something less than $1$.

-

Quote from Daniel Shanks:

Since $\; \log \log \log n \rightarrow \infty \;$ (with great dignity) these inequalities imply...

-