Logarithms give a way to describe large numbers compactly. But sometimes even the logarithm is a huge number, and it would be convenient to take the log again. And maybe again.
For example, consider
googolplex = 10googol
where
googol = 10100.
(The name googol is older than “Google,” and in fact the former inspired the latter name.)
A googolplex is a big number. It’s log base 10 is still a big number. You have to take the log 3 times to get to a small number:
log10( log10( log10 googolplex ) ) = 2.
Log star
The iterated logarithm base b of a positive number x, written log*b (x) is the number of times you have to take the log base b until you get a result less than or equal to 1. So in the example above
log*10 googolplex = 4.
As usual, a missing base implies b = e. Also just as log base 2 is often denoted lg, the iterated log base 2 is sometimes denoted lg*.
I’ve seen sources that say the base of an iterated logarithm doesn’t matter. That’s not true, because, for example,
log*2 googolplex = 6.
The function log*(x) appears occasionally in the analysis of algorithms.
Python implementation
It’s easy to implement the iterated log, though this is of limited use because the iterated log is usually applied to numbers too large to represent as floating point numbers.
from math import log, exp
def logstar(x, base=exp(1)):
c = 0
while x > 1:
x = log(x, base)
c += 1
return c
lgstar = lambda x: logstar(x, 2)
Mersenne primes
The largest known prime, at the time of writing, is
p = 2136279841 − 1.
We can use the code above to determine that lg* 136279841 = 5 and so lg* p = 6.
Skewes’ bounds
The prime number theorem says that the number of prime numbers less than x, denoted π(x), is asymptotically li(x) where
You may have seen a different form of the prime number theorem that says π(x) is asymptotically x/log x. That’s true too, because li(x) and x/log x are asymptotically equal. But li(x) gives a better approximation to π(x) for finite x. More on that here.
For every x for which π(x) has been computed, π(x) < li(x). However, Littlewood proved in 1914 that there exists some x for which π(x) > li(x). In 1933 Stanley Skewes gave an upper bound on the smallest x such that π(x) > li(x), assuming the Riemann Hypothesis:
S1 = 10^(10^(10^34))
In 1955 he proved the upper bound
S2 = 10^(10^(10^964))
not assuming the Riemann Hypothesis.
You can calculate that
log*10 S1 = 5
and
log*10 S2 = 6.
Iterated iterated logarithm
In all the examples above, log*(x) is a small number. But for some numbers, such as Moser’s number and Graham’s number, even log*(x) is unwieldy and you have to do things like take the iterated logarithm of the iterated logarithm
log**(x) = log*( log*(x) )
before the numbers become imaginable.