Double exponential function

A double exponential function (red curve) compared to a single exponential function (blue curve).

A double exponential function is a constant raised to the power of an exponential function. The general formula is a = b = 10:

• f(1) = 10
• f(100) = 10 = googolplex.

Factorials grow faster than exponential functions, but much more slowly than double exponential functions. However, tetration and the Ackermann function grow faster. See Big O notation for a comparison of the rate of growth of various functions.

The inverse of the double exponential function is the double logarithm g(x)=bx=exln⁡b.

n. Examples include

• The Fermat numbers 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/p exceeds 0, 1, 2, 3, …
  MM(p)=22p−1−1
• The elements of Sylvester's sequence E ≈ 1.264084735305302 is Vardi's constant 22k
• The prime numbers 2, 11, 1361, ... A ≈ 1.306377883863 is Mills' constant.

Aho and Sloane observed that in several important integer sequences, each term is a constant plus the square of the previous term. They show that such sequences can be formed by rounding to the nearest integer the values of a double exponential function with middle exponent 2. Ionaşcu and Stănică describe some more general sufficient conditions for a sequence to be the floor of a double exponential sequence plus a constant.

In computational complexity theory, 2-EXPTIME is the class of decision problems solvable in double exponential time. It is equivalent to AEXPSPACE, the set of decision problems solvable by an alternating Turing machine in exponential space, and is a superset of EXPSPACE. An example of a problem in 2-EXPTIME that is not in EXPTIME is the problem of proving or disproving statements in Presburger arithmetic.

In some other problems in the design and analysis of algorithms, double 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 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 n distinct prime factors are known to be at most k ≥ 1 interior lattice points is at most N(y) is the population in millions in year Ionaşcu, Eugen-Julien; Stănică, Pantelimon (2004), "Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences" (PDF), Acta Mathematica Universitatis Comenianae, LXXIII (1): 75–87.

↑ Christos Papadimitriou, Computational Complexity (1994), Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: The Electronic Journal of Combinatorial Number Theory, 3: A14.

↑ Varfolomeyev, S. D.; Gurevich, K. G. (2001), "The hyperexponential growth of the human population on a macrohistorical scale", Journal of Theoretical Biology, 212 (3): 367–372, Bibcode:2001JThBi.212..367V, doi:10.1006/jtbi.2001.2384, PMID 11829357.

↑