A função log estrela (log*)

Vamos supor, nesta página, 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,

(Não confunda a expressão  log(3) x  com  log3 x,  que significa  (log x)3.)   De modo mais geral,

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

 

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

xlog* x
10
21
31
42
52
152
163
655353
655364
10804

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

 

Função 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) = 2T(k−1)

para k = 1, 2, 3,  …     Portanto, T(1) = 2, T(2) = 22, T(3) = 222, T(4) = 2222, e assim por diante.  (Observe que 2222 = 2(2(22)) = 265536 é muito maior que um mero ((22)2)2, que vale 28.)

kT(k)
01
12
24
316
465536
5265536

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

T(k−1) < xT(k).

Por exemplo,  log* 65536 = 4  e  log* 265536 = 5.