Double exponential function

Last updated October 10, 2024

A double exponential function is a constant raised to the power of an exponential function. The general formula is $f(x)=a^{b^{x}}=a^{(b^{x})}$ (where a>1 and b>1), which grows much more quickly than an exponential function. For example, if a = b = 10:

Double exponential sequences

A sequence of positive integers (or real numbers) is said to have double exponential rate of growth if the function giving the $n$ th term of the sequence is bounded above and below by double exponential functions of $n$ . Examples include

The Fermat numbers $F(m)=2^{2^{m}}+1$
The harmonic primes: The primes p, in which the sequence 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/p exceeds 0, 1, 2, 3, …
The first few numbers, starting with 0, are 2, 5, 277, 5195977, ... (sequence A016088 in the OEIS )
The Double Mersenne numbers $MM(p)=2^{2^{p}-1}-1$
The elements of Sylvester's sequence (sequence A000058 in the OEIS ) $s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor$ where E ≈ 1.264084735305302 is Vardi's constant (sequence A076393 in the OEIS ).
The number of k-ary Boolean functions: $2^{2^{k}}$
The prime numbers 2, 11, 1361, ... (sequence A051254 in the OEIS ) $a(n)=\left\lfloor A^{3^{n}}\right\rfloor$ where 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.^[1] 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.^[2]

Applications

Algorithmic complexity

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.^[3] An example of a problem in 2-EXPTIME that is not in EXPTIME is the problem of proving or disproving statements in Presburger arithmetic.^[4]

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 h_i = 2^2ⁱ (estimates for the eventual output size), taking time O(n log h_i) 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.^[5]

Number theory

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).^[6]

The maximal volume of a polytope in a d-dimensional integer lattice with k ≥ 1 interior lattice points is at most

k\cdot (8d)^{d}\cdot 15^{d\cdot 2^{2d+1}},

a result of Pikhurko (2001).^[7]

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.^[8]

Theoretical biology

In population dynamics the growth of human population is sometimes supposed to be double exponential. Varfolomeyev and Gurevich^[9] experimentally fit

N(y)=375.6\cdot 1.00185^{1.00737^{y-1000}}\,

where N(y) is the population in millions in year y.

Physics

In the Toda oscillator model of self-pulsation, the logarithm of amplitude varies exponentially with time (for large amplitudes), thus the amplitude varies as double exponential function of time.^[10]

Dendritic macromolecules have been observed to grow in a doubly-exponential fashion.^[11]

Related Research Articles

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number ⁠ $⁠$ which in modular arithmetic satisfies the congruence relation:

The number $e$ is a mathematical constant approximately equal to 2.71828 that is the base of the natural logarithm and exponential function. It is sometimes called Euler's number, after the Swiss mathematician Leonhard Euler, though this can invite confusion with Euler numbers, or with Euler's constant, a different constant typically denoted $. Alternatively, e can be called Napier's constant after John Napier. The Swiss mathematician Jacob Bernoulli discovered the constant while studying compound interest.$

<span class="mw-page-title-main">Exponential function</span> Mathematical function, denoted exp(x) or e^x

The exponential function is a mathematical function denoted by $or . Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, although it can be extended to the complex numbers or generalized to other mathematical objects like matrices or Lie algebras. The exponential function originated from the operation of taking powers of a number, but various modern definitions allow it to be rigorously extended to all real arguments, including irrational numbers. Its ubiquitous occurrence in pure and applied mathematics led mathematician Walter Rudin to consider the exponential function to be "the most important function in mathematics".$

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, the factorial of a non-negative integer $,$ denoted by $,$ is the product of all positive integers less than or equal to $.$ The factorial of also equals the product of $with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.$

In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $x$ , $y$ , the greatest common divisor of $x$ and $y$ is denoted $. For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4 .$

In mathematics, the logarithm to base $b$ is the inverse function of exponentiation with base $b$ . That means that the logarithm of a number $x$ to the base $b$ is the exponent to which $b$ must be raised to produce $x$ . For example, since $1000 = 10 3$ , the logarithm base $of 1000 is 3, or log 10 (1000) = 3 . The logarithm of x to base b is denoted as log b (x), or without parentheses, log b x . When the base is clear from the context or is irrelevant it is sometimes written log x .$

The natural logarithm of a number is its logarithm to the base of the mathematical constant $e$ , which is an irrational and transcendental number approximately equal to $2.718 281828459$ . The natural logarithm of $x$ is generally written as $ln x$ , $log e x$ , or sometimes, if the base $e$ is implicit, simply $log x$ . Parentheses are sometimes added for clarity, giving $ln(x)$ , $log e (x)$ , or $log(x)$ . This is done particularly when the argument to the logarithm is not a single symbol, so as to prevent ambiguity.

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 3². The smallest positive square-free numbers are

In mathematics, a Fermat number, named after Pierre de Fermat (1607–1665), the first known to have studied them, is a positive integer of the form: $where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ....$

<span class="mw-page-title-main">Exponentiation</span> Arithmetic operation

In mathematics, exponentiation is an operation involving two numbers: the base and the exponent or power. Exponentiation is written as $b n$ , where $b$ is the base and $n$ is the power; this is pronounced as " $b$ (raised) to the $n$ ". When $n$ is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, $b n$ is the product of multiplying $n$ bases:

<span class="mw-page-title-main">Exponential growth</span> Growth of quantities at rate proportional to the current amount

Exponential growth occurs when a quantity grows at a rate directly proportional to its present size. For example, when it is 3 times as big as it is now, it will be growing 3 times as fast as it is now.

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

10 (ten) is the even natural number following 9 and preceding 11. Ten is the base of the decimal numeral system, the most common system of denoting numbers in both spoken and written language.

<span class="mw-page-title-main">Tetration</span> Arithmetic operation

In mathematics, tetration is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though Knuth's up arrow notation $and the left-exponent x b are common.$

In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number in which every prime factor is at most 7. Therefore, 49 = 7² and 15750 = 2 × 3² × 5³ × 7 are both 7-smooth, while 11 and 702 = 2 × 3³ × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. 2-smooth numbers are simply the powers of 2, while 5-smooth numbers are also known as regular numbers.

<span class="mw-page-title-main">Sylvester's sequence</span> Doubly exponential integer sequence

In number theory, Sylvester's sequence is an integer sequence in which each term is the product of the previous terms, plus one. Its first few terms are

Regular numbers are numbers that evenly divide powers of 60 (or, equivalently, powers of 30). Equivalently, they are the numbers whose only prime divisors are 2, 3, and 5. As an example, 60² = 3600 = 48 × 75, so as divisors of a power of 60 both 48 and 75 are regular.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

References

↑ Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly , 11: 429–437.
↑ 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), ISBN 978-0-201-53082-7. Section 20.1, corollary 3, page 495.
↑ Fischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic. Archived 2006-09-15 at the Wayback Machine " Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41
↑ Chan, T. M. (1996), "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete and Computational Geometry , 16 (4): 361–368, doi: 10.1007/BF02712873 , MR 1414961
↑ Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: The Electronic Journal of Combinatorial Number Theory, 3: A14.
↑ Pikhurko, Oleg (2001), "Lattice points in lattice polytopes", Mathematika , 48 (1–2): 15–24, arXiv: math/0008028 , Bibcode:2000math......8028P, doi:10.1112/s0025579300014339
↑ Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature , 168 (4280): 838, Bibcode:1951Natur.168..838M, doi: 10.1038/168838b0 .
↑ 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 .
↑ Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), "Self-pulsing laser as oscillator Toda: Approximation through elementary functions", Journal of Physics A , 40 (9): 1–18, Bibcode:2007JPhA...40.2107K, CiteSeerX 10.1.1.535.5379 , doi:10.1088/1751-8113/40/9/016, S2CID 53330023 .
↑ Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). "Double Exponential Dendrimer Growth". Journal of the American Chemical Society . 117 (8): 2159–2165. doi:10.1021/ja00113a005.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly , 11: 429–437.

[2] 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.

[3] Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7. Section 20.1, corollary 3, page 495.

[4] Fischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic. Archived 2006-09-15 at the Wayback Machine " Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41

[5] Chan, T. M. (1996), "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete and Computational Geometry , 16 (4): 361–368, doi: 10.1007/BF02712873 , MR 1414961

[6] Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: The Electronic Journal of Combinatorial Number Theory, 3: A14.

[7] Pikhurko, Oleg (2001), "Lattice points in lattice polytopes", Mathematika , 48 (1–2): 15–24, arXiv: math/0008028 , Bibcode:2000math......8028P, doi:10.1112/s0025579300014339

[8] Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature , 168 (4280): 838, Bibcode:1951Natur.168..838M, doi: 10.1038/168838b0 .

[9] 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 .

[kouz-10] Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), "Self-pulsing laser as oscillator Toda: Approximation through elementary functions", Journal of Physics A , 40 (9): 1–18, Bibcode:2007JPhA...40.2107K, CiteSeerX 10.1.1.535.5379 , doi:10.1088/1751-8113/40/9/016, S2CID 53330023 .

[11] Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). "Double Exponential Dendrimer Growth". Journal of the American Chemical Society . 117 (8): 2159–2165. doi:10.1021/ja00113a005.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]