雙重指數

维基百科,自由的百科全书
跳转至: 导航搜索
雙重指數函數(紅色)和一般實數指數冪(藍色)的比較

雙重指數函數是指公式為f(x) = a^{b^x}函數,是指數為另一個指數冪的指數,在x<0時,雙重指數函數接近1,但當x>0時,雙重指數函數成長速率比指數函數還要快。

例如a = b = 10時:

階乘的成長速度比指數函數還快,但比雙重指數函數慢很多。而迭代冪次阿克曼函數的成長速度比雙重指數函數要快很多。

雙重指數數列[编辑]

以下是一些和雙重指數有關的數列:

2^{2^n}
F(m) = 2^{2^m}+1
MM(p) = 2^{2^p-1}-1

Aho和Sloane發現有許多整數數列的每一項是前一項的平方再加上一個整數,這類的數列常常可以用最接近雙重指數數列的整數來表示,且雙重指數數列中間的指數為2[1]。若一整數數列的第n項和n的雙重指數成正比,Ionascu 及Stanica將這樣的整數數列稱為「幾乎雙重指數」(almost doubly-exponential),可以定義為雙重指數加上一常數後再取整數[2]

s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor
其中E ≈ 1.264084735305302為Vardi常數。
a(n) = \left\lfloor A^{3^n}\right\rfloor
其中A ≈ 1.306377883863為米尔斯常数

應用[编辑]

演算法複雜度[编辑]

計算複雜性理論中,有些演算法時間複雜度是雙重指數,例如:

數論[编辑]

有些數論中的上限是雙重指數,例如有n個相異質數的奇完全數的上限為[4]

2^{4^n}

自從Miller和Wheeler在1951年利用EDSAC找到79位數的質數之後.利用電腦找到的已知最大質數英语largest known prime number和年份之間的關係為雙重指數函數[5]

參考資料[编辑]

  1. ^ Aho, A. V.; Sloane, N. J. A., Some doubly exponential sequences, Fibonacci Quarterly. 1973, 11: 429–437 
  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. Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), 5126. 2008: pp. 39–50. doi:10.1007/978-3-540-70583-3_4. 
  4. ^ Nielsen, Pace P., An upper bound for odd perfect numbers, INTEGERS: the Electronic Journal of Combinatorial Number Theory. 2003, 3: A14 .
  5. ^ Miller, J. C. P.; Wheeler, D. J., Large prime numbers, Nature. 1951, 168 (4280): 838, doi:10.1038/168838b0, Bibcode 1951Natur.168..838M .