双重指数函数

双重指数函数是指公式为${\displaystyle 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元逻辑运算符的个数：

${\displaystyle 2^{2^{n}}}$

• 费马数

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

• 双重梅森数

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

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

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

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

其中E ≈ 1.264084735305302为Vardi常数。

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

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

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

应用

算法复杂度

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

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

数论

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

${\displaystyle 2^{4^{n}}}$

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

参考资料

1. Aho, A. V.; Sloane, N. J. A., Some doubly exponential sequences, Fibonacci Quarterly, 1973, 11: 429–437 [2013-01-22], （原始内容存档于2021-05-06）
2. Ionascu, E.; Stanica, P., Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences, Acta Mathematica Universitatis Comenianae, 2004, LXXIII (1): 75–87.
3. Gruber, Hermann; Holzer, Markus. Finite Automata, Digraph Connectivity, and Regular Expression Size (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008) 5126: 39–50. 2008 [2013-01-23]. doi:10.1007/978-3-540-70583-3_4. （原始内容存档 (PDF)于2011-07-11）.
4. Nielsen, Pace P., An upper bound for odd perfect numbers, INTEGERS: the Electronic Journal of Combinatorial Number Theory, 2003, 3: A14 [2013-01-23], （原始内容存档于2017-03-21）.
5. Miller, J. C. P.; Wheeler, D. J., Large prime numbers, Nature, 1951, 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0.