Logaritmo iterado

El término logaritmo iterado se refiere, en términos matemáticos, a una función definida por la aplicación repetida (iterada) de la función logaritmo sobre su argumento. Así, puede ser descrita como el número de veces que es necesario aplicar logaritmo para obtener un valor de uno (1), o menor.

La función de logaritmo iterado, denotada como log*(x) (o las formas ln*(x), lg*(x), log*(x), cuando no se pueda discernir la base en el contexto), puede ser definida recursivamente como:

${\displaystyle \log ^{\star }:\mathbb {R} \to \mathbb {N} _{0}}$

${\displaystyle \log ^{\star }(x)={\begin{cases}0,&{\mbox{si }}x\leq 1\\1+\log ^{\star }(\log x),&{\mbox{si }}x>1\end{cases}}}$

donde ${\displaystyle \mathbb {N} _{0}}$ es el conjunto de los números naturales, más el cero, es decir: ${\displaystyle \mathbb {N} \cup \{0\}}$ (aquí se ha considerado que los naturales no incluyen el cero, aunque la tendencia más reciente, unida al uso en informática, dispone lo contrario).

Esta función es monótonamente no-decreciente, con tasa decreciente. Es decir, el valor de ${\displaystyle \log ^{\star }(x+1)}$ es siempre igual o mayor que el valor de ${\displaystyle \log ^{\star }(x)}$.

Una característica peculiar de lg* es que esta función es de muy lento crecimiento. Mientras que lg*(1) = 1, y para un argumento en las centenas el logaritmo iterado podría devolver valores de 3 o 4, para un número tan grande como ${\displaystyle 2^{2^{16}}=2^{65536}}$, que es mucho más que el número de partículas de materia estimados en el Universo observable, apenas sí alcanza valores de 6 o 7.

Para efectos prácticos al considerar valores de x, ${\displaystyle \log ^{\star }(x)}$ puede considerarse una constante.

La notación especial ${\displaystyle \ln ^{\star }(x)}$ es usada para el "logaritmo natural iterado" (el logaritmo aplicado usando base ${\displaystyle e}$). La notación especial ${\displaystyle \lg ^{\star }(x)}$ es usada en el contexto de la informática para "logaritmo binario iterado", que itera la función logaritmo en base dos (muy común en el área de la informática).

Expresiones haciendo uso de logaritmo iterado aparecen en análisis de algoritmos como por ejemplo la triangulación de Delaunay, y en algoritmos relacionados con grafos y árboles.

• Logaritmo
• Logaritmo natural
• Hiperoperación
• Tetración

• Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) . Introduction to Algorithms (2nd edición). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.  La referencia utiliza el parámetro obsoleto |coautores= (ayuda)