Iterated Logarithm

The iterated logarithm is a function that counts the number of times the logarithm must be iteratively taken to give a result that is less than or equal to 1. The iterated logarithm of x is written lg*x.

First define the function lgn:

	
lg0x = x 
lgnx = lg(lgn-1x)
lgnx = undefined if n>0 and lgn-1x≤0 or lgn-1x is undefined
	.
      

The definition of lg*:

	
lg*x = min{n≥0|lgnx≤1} 
	.
      

An alternative definition:

	
lg*x = 0          if x≤1,
lg*x = 1+lg*(lg x) otherwise
	.
      

Note that the iterated logarithm grows very slowly.

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.