tetrationとiterated logarithm

　tetrationとiterated logarithm。
それぞれ演算の種類です。見たことはありましたが、理解が曖昧だったので調べてみました。

tetrationとは?

ⁿa = 1 if n = 0
ⁿa = a^(^(n-1)a) if n > 0

で定義される演算です。

⁰2 = 1
¹2 = 2^(⁰2) = 2
²2 = 2^(¹2) = 4
³2 = 2^(²2) = 16
⁴2 = 2^(³2) = 65536
⁵2 = 2^(⁴2) = 2^65536
......

のようになり、ものすごい早さで増加する関数です。

a * n = a + a + a + a + ....というように掛け算は足し算に分解できます。
同様に、
a ^ n = a * a * a * a * ... というようにべき乗は掛け算に分解できます。

tetrationの場合は、
ⁿa = a^(a^(a^(a^....)))というようにべき乗に分解できます。 例えば⁴2 = 2^(2^(2^2)) = 2^(2^4) = 2 ^ 16 = 65536というふうになります。

iterated logarithmとは?

iterated logarithmとは以下のように定義される関数です。

log*(n) = 0 if n <= 1
log*(n) = 1 + log*(log(n)) if n > 1

log*()は一般に"log star"と読みます。

例えば底を2とすると、
log*(1) = 0
log*(2) = 1 + log*(log(2)) = 1 + log*(1) = 1
log*(4) = 1+ log*(log(4)) = 1 + log*(2) = 2
log*(16) = 1 + log*(log(16)) = 1 + log*(4) = 3
log*(65536) = 1 + log*(log(65536)) = 1 + log*(16) = 4
log*(2^65536) = 1 + log*(log(2^65536)) = 1 + log*(65536) = 5

となります。ちょうどtetrationの逆関数のような関係（※）にあり、ものすごく増加の遅い関数です。

※厳密にはtetrationの逆関数はsuper-logarithmです。
正の実数nに対して、super-logarithmとiterated logarithmには
log*n = ceil(slog(n))
という関係が成り立ちます。