Iterated logarithm

In computer science, the iterated logarithm of n {\displaystyle n} , written log* n {\displaystyle n} (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1 {\displaystyle 1} . The simplest formal definition is the result of this recurrence relation: log ∗ ⁡ n := { 0 if n ≤ 1 ; 1 + log ∗ ⁡ ( log ⁡ n ) if n > 1 {\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}} In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm (with base 2 {\displaystyle 2} ) instead of the natural logarithm (with base e). Mathematically, the iterated logarithm is well defined for any base greater than e 1 / e ≈ 1.444667 {\displaystyle e^{1/e}\approx 1.444667} , not only for base 2 {\displaystyle 2} and base e. The "super-logarithm" function s l o g b ( n ) {\displaystyle \mathrm {slog} _{b}(n)} is "essentially equivalent" to the base b {\displaystyle b} iterated logarithm (although differing in minor details of rounding) and forms an inverse to the operation of tetration.