反復対数

${\displaystyle n}$ についての反復対数は ${\displaystyle \log ^{*}n}$（ログスター ${\displaystyle n}$）と表記され、単純には次のように再帰的に定義される。

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}$

関数の反復を用いれば、次のようにも定義できる。

${\displaystyle \log ^{*}n:=\min \left\{i\geq 0:\log ^{(i)}n\leq 1\right\}}$

正の実数においては、連続性の超対数（英語版）に等しい。

${\displaystyle \log ^{*}n=\lceil \mathrm {slog} \,n\rceil }$

言い換えれば、${\displaystyle b}$ を反復対数の底として、${\displaystyle n}$ が区間 ${\displaystyle (^{y-1}b,\,^{y}b]}$ にあるとき、その反復対数は ${\displaystyle \log _{b}^{*}n=y}$ で表される。ここで ${\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}}$ はテトレーションである。ただし、負の実数 ${\displaystyle x}$ について、反復対数の値は ${\displaystyle \log ^{*}x=0}$ であるが、${\displaystyle \lceil \mathrm {slog} \,x\rceil =-1}$ であるので、負の実数においては先に示した関係は成り立たないことになる。

反復対数は実数全体で定義され、非負整数を値域にとる。正の実数に対しては、${\displaystyle xy}$ 平面の図1において ${\displaystyle x}$ 軸上の区間 ${\displaystyle (0,1]}$ に到達するために必要なジグザグの数として図式的に理解できる。

計算機科学においては、自然対数の代わりに二進対数を反復する反復対数 ${\displaystyle \lg ^{*}n:=\log _{2}^{*}n}$ も用いられている。数学的には、${\displaystyle e}$ や ${\displaystyle 2}$ だけでなく、${\displaystyle e^{1/e}\approx 1.444667}$ より大きい任意の底に対してwell-definedである。