二重指数関数
二重指数関数(にじゅうしすうかんすう、double exponential function)とは、指数関数の肩に指数関数を持つ関数である。一般形は f(x) = a^{b^x}=a^{(b^x)}。
指数関数と同様に、二重指数関数型積分公式など、応用上はネイピア数を底に取ったものがよく使われる。
指数の底が a > 1, b > 1 を満たすなら、二重指数関数は通常の指数関数よりも速く大きくなる。
また二重指数関数は階乗より急速に増大する。階乗は通常の(一重の)指数関数よりも速く増大するため、充分大きい x について以下の関係が成り立つ(e はネイピア数):
e^x<x!<e^{e^x}
二重指数関数に比べて速く増大する関数として、例えばテトレーションとアッカーマン関数がよく知られている(その他さまざまな関数の増加率ついては例えばランダウの記号を参照のこと)。
二重指数関数 a^{b^x} の逆関数は、二重対数 \log_{b}(\log_{a}x) である。
正の整数(または実数)の数列で、数列のn番目の項を与える関数がnの二重指数関数で上下を押さえられるものを、二重指数関数的に成長する数列という。
F(m)=2^{2^m}+1
調和素数:1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / pが0、1、2、3、..を超える素数p 0で始まる最初のいくつかの番号は、2、5、277、5195977、...(A016088)である。
MM(p)=2^{2^{p-1}-1
シルベスター数列の要素(A000058)
s_n=\left \lfloor E^{2^{n+1}+\frac{1}{2} \right \rfloor
なお、E ≈ 1.264084735305302 はヴァルディの定数(A076393)である
k-aryブール関数:
2^{2^k}
素数 2, 11, 1361, ... (A051254)
a(n)=\left \lfloor A^{3^n} \right \rfloor
なお、A ≈ 1.306377883863はミルズの定数である。
アルフレッド・エイホとニール・スローンは、いくつかの重要な整数列で、各項が定数に前の項の2乗を加えたものであることを観察した。それらは、そのような数列が、中間の指数2を持つ二重指数関数の値を最も近い整数に丸めることによって形成できることを示している IonaşcuとStănicăは、数列が二重指数列と定数のフロアになるためのより一般的な十分条件について説明している。
{d \over dx}e^{e^x}=e^x*e^{e^x}
\int e^{e^x}\operatorname{d}\!x
In computational complexity theory, some algorithms take doubly exponential time:
Each decision procedure for Presburger arithmetic provably requires at least doubly exponential time
Computing a Gröbner basis over a field. In the worst case, a Gröbner basis may have a number of elements which is doubly exponential in the number of variables. On the other hand, the worst-case complexity of Gröbner basis algorithms is doubly exponential in the number of variables as well as in the entry size.
Finding a complete set of associative-commutative unifiers
Satisfying CTL+ (which is, in fact, 2-EXPTIME-complete)
Quantifier elimination on real closed fields takes doubly exponential time (see Cylindrical algebraic decomposition).
Calculating the complement of a regular expression
In some other problems in the design and analysis of algorithms, doubly exponential sequences are used within the design of an algorithm rather than in its analysis. An example is Chan's algorithm for computing convex hulls, which performs a sequence of computations using test values hi = 22i (estimates for the eventual output size), taking time O(n log hi) for each test value in the sequence. Because of the double exponential growth of these test values, the time for each computation in the sequence grows singly exponentially as a function of i, and the total time is dominated by the time for the final step of the sequence. Thus, the overall time for the algorithm is O(n log h) where h is the actual output size.
Some number theoretical bounds are double exponential. Odd perfect numbers with n distinct prime factors are known to be at most
2^{4^n}
a result of Nielsen (2003). The maximal volume of a d-lattice polytope with k ≥ 1 interior lattice points is at most
(8d)^d\cdot15^{d\cdot2^{2d+1}
a result of Pikhurko.
The largest known prime number in the electronic era has grown roughly as a double exponential function of the year since Miller and Wheeler found a 79-digit prime on EDSAC1 in 1951.
In population dynamics the growth of human population is sometimes supposed to be double exponential. Varfolomeyev and Gurevich experimentally fit
N(y)=375.6\cdot 1.00185^{1.00737^{y-1000} \,
where N(y) is the population in millions in year y.
In the Toda oscillator model of self-pulsation, the logarithm of amplitude varies exponentially with time (for large amplitudes), thus the amplitude varies as doubly exponential function of time.
Dendritic macromolecules have been observed to grow in a doubly-exponential fashion.