Iterated logarithm

In computer science, the iterated logarithm of $n$ , written log* $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$ .^[1] The simplest formal definition is the result of this recurrence relation:

\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$ ) instead of the natural logarithm (with base e). Mathematically, the iterated logarithm is well defined for any base greater than $e^{1/e}\approx 1.444667$ , not only for base $2$ and base e. The "super-logarithm" function $\mathrm {slog} _{b}(n)$ is "essentially equivalent" to the base $b$ iterated logarithm (although differing in minor details of rounding) and forms an inverse to the operation of tetration.^[2]

^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "The iterated logarithm function, in Section 3.2: Standard notations and common functions". Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 58–59. ISBN 0-262-03384-4.
^ Furuya, Isamu; Kida, Takuya (2019). "Compaction of Church numerals". Algorithms. 12 (8) 159: 159. doi:10.3390/a12080159. MR 3998658.

[1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "The iterated logarithm function, in Section 3.2: Standard notations and common functions". Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 58–59. ISBN 0-262-03384-4.

[2] Furuya, Isamu; Kida, Takuya (2019). "Compaction of Church numerals". Algorithms. 12 (8) 159: 159. doi:10.3390/a12080159. MR 3998658.

[1]

[2]