双重指数函数

双重指数函数是指公式为$f(x)=a^{b^{x}}$的函数，是指数为另一个指数幂的指数幂，在x<0时，双重指数函数接近1，但当x>0时，双重指数函数成长速率比指数函数还要快。

双重指数函数（红色）和一般实数指数幂（蓝色）的比较

例如a = b = 10时：

• f(−1) ≈ 1.26
• f(0) = 10
• f(1) = 10¹⁰
• f(2) = 10¹⁰⁰ = 古高尔（googol）
• f(3) = 10¹⁰⁰⁰
• f(100) = 10¹⁰¹⁰⁰ = 古戈尔普勒克斯（googolplex）

阶乘的成长速度比指数函数还快，但比双重指数函数慢很多。而迭代幂次和阿克曼函数的成长速度比双重指数函数要快很多。

双重指数数列

以下是一些和双重指数有关的数列：

• n元逻辑运算符的个数：

$2^{2^{n}}$

• 费马数

$F_{m}=2^{2^{m}}+1$

• 双重梅森数

$M_{M_{p}}=2^{2^{p}-1}-1$

Aho和Sloane发现有许多整数数列的每一项是前一项的平方再加上一个整数，这类的数列常常可以用最接近双重指数数列的整数来表示，且双重指数数列中间的指数为2。若一整数数列的第n项和n的双重指数成正比，Ionascu 及Stanica将这样的整数数列称为“几乎双重指数”（almost doubly-exponential），可以定义为双重指数加上一常数后再取整数。

• 西尔维斯特数列（OEIS数列A000058）

$s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor$

其中E ≈ 1.264084735305302为Vardi常数。

• 质数2, 11, 1361, ... （OEIS数列A051254）

$a(n)=\left\lfloor A^{3^{n}}\right\rfloor$

其中A ≈ 1.306377883863为米尔斯常数。

应用

算法复杂度

在计算复杂性理论中，有些算法的时间复杂度是双重指数，例如：

• 在实闭域中的量词消去。
• 计算正则表达式的差集。

数论

有些数论中的上限是双重指数，例如有n个相异质数的奇完全数的上限为：

$2^{4^{n}}$

自从Miller和Wheeler在1951年利用EDSAC找到79位数的质数之后．利用电脑找到的已知最大质数和年份之间的关系为双重指数函数。