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.

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?

share|improve this question
    
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
5  
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
1  
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

Quote from Daniel Shanks:

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

share|improve this answer

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.