A função log estrela (log*)

Vamos supor, neste capítulo, que log x denota o logaritmo de x na base 2.  Mas tudo vale, com os ajustes óbvios, para qualquer outra base.

Logaritmo iterado.  Para qualquer x,

• log⁽¹⁾ x = log x
• log⁽²⁾ x = log log x = log (log x)
• log⁽³⁾ x = log log log x = log (log (log x))

(Não confunda  log⁽³⁾ x  com  log³ x,  que significa  (log x)³.)   De modo mais geral,

• log^(k) x  =  log log^(k−1) x

para todo inteiro k ≥ 2.   É claro que log^(k) x só está definido para x ≥ 2^k−1 pois  log^(k) 2^k−1 = 0 .

Log estrela.  Para qualquer  x,   log* x   é o menor  k  tal que  log^(k) x  ≤  1.

Como se vê, log* x cresce muuuito deeevaaagaaar com x.

Torre exponencial.  Outra maneira de apresentar a definição de log* começa com a função T definida assim:  T(0) = 1  e

T(k) = 2^T(k−1)

para k = 1, 2, 3, …    Portanto, T(1) = 2, T(2) = 2², T(3) = 2²², T(4) = 2²²², e assim por diante.  (Observe que 2²²² = 2^(2(22)) = 2⁶⁵⁵³⁶ é muito maior que um mero ((2²)²)², que vale 2⁸.)

Agora, podemos dizer que  log* x  é o único número inteiro k tal que

T(k−1) < x ≤ T(k).

Por exemplo,  log* 65536 = 4  e  log* 2⁶⁵⁵³⁶ = 5.