Iterated logarithm
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 starThe 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 impliesb =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 implementationIt'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, expdef logstar(x, base=exp(1)): c = 0 while x > 1: x = log(x, base) c += 1 return clgstar = 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' boundsThe 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 asymptoticallyx/logx. That's true too, because li(x) andx/logx are asymptotically equal. But li(x) gives a better approximation to (x) for finitex. More on that here.
For everyx for which (x) has been computed, (x) < li(x). However, Littlewood proved in 1914 that there exists some xfor 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 logarithmIn 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.
Related postsThe post Iterated logarithm first appeared on John D. Cook.