The **iterated logarithm function**log * *n *(“log star of n”) is defined as the smallest natural number *k *for which

log^{(i)} ≤ 1.

The function is not defined for n < 1.

Formally, it is defined as [1]:

- log * n = 0 if n ≤ 1
- log * n = 1 + log * (log n) if n > 1.

This slow growing function measures how many times you have to take the logarithm of *n *before it drops to one [2] or how many times you can take the log *n *base of a number [3].

A few examples:

- log * 1 = 0
- log * 2 = 1
- log * 4 = 2
- log * 16 = 3
- log * 65,536 = 4.
- log * (2
^{65536}) = 5

This function is very slow-growing. Since the number of atoms in the universe if about 10^{80}, which is a lot less than 2^{65536}, it’s very rare to see any use the iterated logarithm function for numbers that high: lg * 10^{20} exceeds the number of bytes in all of the computers on the planet [2].

Uses include algorithm analysis and building search trees (the Union-Find algorithm) in computer science, probability theory [4], mathematical systems and control theory [5], as well as various mathematical areas like the study of sets in bounded systems.

## Iterated Logarithm Function & Tower-of-2

The iterated logarithm function is the inverse of the tower-of-2 function (similar to how log^{2}x is the inverse of 2^{x}). The first few towers-of-2:

- tower-of-2(1) = 2
- tower-of-2(2) = 2
^{2}= 4 - tower-of-2(3) = 16
- tower-of-2(4) = 65,536
- tower-of-2(5) ≈ 1000
^{6,553}

As this is the inverse of the iterated logarithm function, it grows very slowly. If you’re trying to calculate log * n by hand, it’s often much easier to calculate tower-of-2 first, then compare the number in question to see which “bucket” it falls into [6].

## References

[1] 600.363 Introduction to Algorithms / 600.463 Algorithms I

[2] Problem Set 1: RMQ.

[3] Disjoint Set Data Structure.

[4] Eichelsbacher, P. & Lowe, M. Workshop on Probability Theory and Its Applications. Retrieved July 31, 2021 from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.7719&rep=rep1&type=pdf

[5] Blondel, V. & Megretski, A. [Eds.]. Unsolved Problems in Mathematical Systems and Control Theory. Retrieved July 31, 2021 from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.1462&rep=rep1&type=pdf

[6] Elkins, D. (2017). Computing the Iterated Logarithm (log-star) by hand. Retrieved July 31, 2021 from: https://math.stackexchange.com/questions/2553258/computing-the-iterated-logarithm-log-star-by-hand

**CITE THIS AS:**

**Stephanie Glen**. "Iterated Logarithm Function" From

**CalculusHowTo.com**: Calculus for the rest of us! https://www.calculushowto.com/iterated-logarithm-function/

**Need help with a homework or test question? **With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!