Intuición para la función iterada para registro registro registro n.

Question

Intuitivamente, $\log n$ (base 2) es el número de veces que se ha de dividir a la $n$ 2 antes de llegar a un número de alrededor de 2. (Agitando nuestras manos un poco de gloss sobre el piso vs techo y $\pm$ 1 errores). Del mismo modo, $\log \log n$ es el número de veces que tenemos que iterar la función de raíz cuadrada para obtener de $n$ hasta un número de alrededor de $2$ (agitando nuestras manos de nuevo).

¿Qué es la intuición para $\log \log \log n$? ¿Cuál es la función que iba a recorrer $\log \log \log n$ veces para que te de $n$ hasta un pequeño constante?

Answer 1

Cito a Daniel Shanks:

Desde $ \; \log \log \log n \rightarrow \infty \;$ (con mucha dignidad) estas desigualdades implican...

Answer 2

Para $\log$, usted tiene $n \mapsto n/2$, que en realidad es $n\mapsto\exp(\log n - 1)$ donde $\exp$ es la exponenciación con base $2$, es decir,$n\mapsto 2^n$ : -)

Para $\log\circ\log$, usted tiene $n\mapsto\sqrt n=\exp\big(\!\frac{\log n}2\!\big)=\exp\exp(\log\log n - 1)$.

Así, por $\log\circ\log\circ\log$, tendrás $n\mapsto\exp\exp\exp(\log\log\log n - 1)$, lo que simplifica... $$n\mapsto2^\sqrt{\log_2 n}.$$ No muy bonito, me temo.

Edit: En retrospectiva, es evidente que si se desea una iteración que toma alrededor de $f(n)$ pasos para llegar a un cierto valor, entonces todo lo que necesita hacer es disminuir el $f(n)$ por una cantidad fija por cada iteración. Así que si la iterada de la función es $n \mapsto m$, se puede elegir $f(m) = f(n)-1$, lo $m = f^{-1}(f(n)-1)$. Por ejemplo, se debe tomar alrededor de $\sqrt n$ iteraciones de $n\mapsto(\sqrt n-1)^2=n-2\sqrt n+1$ mapa de $n$ a algo menos de $1$.