雙重指數函數

雙重指數函數是指公式為${\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 .