Dubbel exponentialfunktion

En dubbel exponentialfunktion (röd kurva) jämfört med en enkel exponentialfunktion (blå kurva).

En dubbel exponentialfunktion är en konstant som höjs till en exponentialfunktions potens . Den allmänna formeln är ${\displaystyle f(x)=a^{b^{x}}=a^{(b^{x})}} ($ där a >1 och b >1), som växer mycket snabbare än en exponentialfunktion. Till exempel, om a = b = 10:

• f (x) = 10 ^{10 x}
• f (0) = 10
• f (1) = 10 ¹⁰
• f (2) = 10 ¹⁰⁰ = googol
• f (3) = 10 ¹⁰⁰⁰
• f (100) = 10 ^{10 100} = googolplex .

Faktorer växer snabbare än exponentialfunktioner, men mycket långsammare än dubbla exponentialfunktioner. Tetration och Ackermann-funktionen växer dock snabbare. Se Big O notation för en jämförelse av tillväxthastigheten för olika funktioner.

Inversen av den dubbla exponentialfunktionen är den dubbla logaritmen log(log( x )).

Dubbelt exponentiella sekvenser

En sekvens av positiva heltal (eller reella tal) sägs ha dubbla exponentiella tillväxthastigheter om funktionen som ger den n :te termen i sekvensen begränsas ovanför och under av dubbla exponentialfunktioner av n . Exempel inkluderar

• Fermat -siffrorna
  $$F(m)=2^{2^{m}}+1$$
• Övertonsprimtal: Primtal p , där sekvensen 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/ p överstiger 0, 1, 2, 3, … De första talen, som börjar med 0, är ​​2, 5, 277, 5195977, ... (sekvens A016088 i OEIS )
• Dubbla Mersenne-siffrorna
  $$MM(p)=2^{2^{p}-1}-1$$
• Elementen i Sylvesters sekvens (sekvens A000058 i OEIS )
  $$s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\ rfloor$$
  där E ≈ 1,264084735305302 är Vardis konstant (sekvens A076393 i OEIS ).
• Antalet k -ary booleska funktioner :
  $$2^{2^{k}}$$
• Primtalen 2, 11, 1361, ... (sekvens A051254 i OEIS )
  $$a(n)=\left\lfloor A^{3^{n}}\right\rfloor$$
  där A ≈ 1,306377883863 är Mills konstant .

Aho och Sloane observerade att i flera viktiga heltalssekvenser är varje term en konstant plus kvadraten på föregående term. De visar att sådana sekvenser kan bildas genom att avrunda till närmaste heltal värdena för en dubbelexponentiell funktion med mittexponent 2. Ionaşcu och Stănică beskriver några mer generella tillräckliga villkor för att en sekvens ska vara golvet i en dubbelexponentiell sekvens plus en konstant .

Ansökningar

Algoritmisk komplexitet

I beräkningskomplexitetsteori är 2-EXPTIME klassen av beslutsproblem som kan lösas i dubbel exponentiell tid . Det motsvarar AEXPSPACE, uppsättningen beslutsproblem som kan lösas av en alternerande Turing-maskin i exponentiellt rymden, och är en superuppsättning av EXPSPACE . Ett exempel på ett problem i 2-EXPTIME som inte är i EXPTIME är problemet med att bevisa eller motbevisa påståenden i Presburger aritmetik .

I vissa andra problem i design och analys av algoritmer används dubbla exponentiella sekvenser inom designen av en algoritm snarare än i dess analys. Ett exempel är Chans algoritm för att beräkna konvexa skrov , som utför en sekvens av beräkningar med testvärden h _i = 2 ^{2 i} (uppskattningar för den slutliga utdatastorleken), och tar tid O( n log h _i ) för varje testvärde i sekvensen . På grund av den dubbla exponentiella tillväxten av dessa testvärden, växer tiden för varje beräkning i sekvensen exponentiellt enskilt som en funktion av i, och den totala tiden domineras av tiden för det sista steget i sekvensen. Således är den totala tiden för algoritmen O( n log h ) där h är den faktiska utdatastorleken.

Talteori

Vissa talteoretiska gränser är dubbelexponentiella. Udda perfekta tal med n distinkta primtalsfaktorer är kända för att vara högst ${\displaystyle 2^{4^{n}}} ,$ ett resultat av Nielsen (2003).

Den maximala volymen av en polytop i ett d -dimensionellt heltalsgitter med k ≥ 1 inre gitterpunkter är som mest

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

ett resultat av Pikhurko (2001).

Det största kända primtalet i den elektroniska eran har vuxit ungefär som en dubbel exponentiell funktion av året sedan Miller och Wheeler hittade ett 79-siffrigt primtal på EDSAC 1 1951.

Teoretisk biologi

I befolkningsdynamik antas tillväxten av mänsklig befolkning ibland vara dubbelexponentiell. Varfolomeyev och Gurevich passade experimentellt

$N(y)=375,6\cdot 1,00185^{1,00737^{y-1000}}\,$

där N ( y ) är befolkningen i miljoner år y .

Fysik

I Toda-oscillatormodellen för självpulsering varierar amplitudens logaritm exponentiellt med tiden (för stora amplituder), sålunda varierar amplituden som en dubbel exponentiell funktion av tiden.

Dendritiska makromolekyler har observerats växa på ett dubbelt exponentiellt sätt.