Iterated logarithm

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the iterated logarithm of 
 
 
 
 n
 
 
 {\displaystyle n}
 
, written log* 
 
 
 
 n
 
 
 {\displaystyle n}
 
 (usually read "log star"), is the number of times the <a href="/facts/Logarithm/QeXaV97q">logarithm</a> function must be <a href="/facts/Iteration/AMc1p7BL">iteratively</a> applied before the result is less than or equal to 
 
 
 
 1
 
 
 {\displaystyle 1}
 
. The simplest formal definition is the result of this <a href="/facts/Recurrence_relation/JolXC71M">recurrence relation</a>:

log
          
            ∗
          
        
        ⁡
        n
        :=
        
          
            {
            
              
                
                  0
                
                
                  
                    
                      if 
                    
                  
                  n
                  ≤
                  1
                  ;
                
              
              
                
                  1
                  +
                  
                    log
                    
                      ∗
                    
                  
                  ⁡
                  (
                  log
                  ⁡
                  n
                  )
                
                
                  
                    
                      if 
                    
                  
                  n
                  >
                  1
                
              
            
            
          
        
      
    
    {\displaystyle \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 <a href="/facts/Binary_logarithm/Uy7kAtRm">binary logarithm</a> (with base 
 
 
 
 2
 
 
 {\displaystyle 2}
 
) instead of the natural logarithm (with base e). Mathematically, the iterated logarithm is well defined for any base greater than 
 
 
 
 
 e
 
 1
 
 /
 
 e
 
 
 ≈
 1.444667
 
 
 {\displaystyle e^{1/e}\approx 1.444667}
 
, not only for base 
 
 
 
 2
 
 
 {\displaystyle 2}
 
 and base e. The "super-logarithm" function 
 
 
 
 
 
 s
 l
 o
 g
 
 
 b
 
 
 (
 n
 )
 
 
 {\displaystyle \mathrm {slog} _{b}(n)}
 
 is "essentially equivalent" to the base 
 
 
 
 b
 
 
 {\displaystyle b}
 
 iterated logarithm (although differing in minor details of <a href="/facts/Rounding/rCLYXN00">rounding</a>) and forms an inverse to the operation of <a href="/facts/Tetration/5rKeVVYv">tetration</a>.

Iterated logarithm open-in-new

Iterated logarithm