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,

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 a expressão log⁽³⁾ x com log³ x, que significa (log x)³.) De modo mais geral,

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

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

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

`x`	log* `x`
1	0
2	1
3	1
4	2
5	2
⋮	⋮
15	2
16	3
⋮	⋮
65535	3
65536	4
⋮	⋮
10⁸⁰	4
⋮	⋮

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) = 2^T(k−1)

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

`k`	`T`(`k`)
0	1
1	2
2	4
3	16
4	65536
5	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.