Dupla exponenciális függvény - Double exponential function

Kettős exponenciális függvény (piros görbe) egyetlen exponenciális függvényhez (kék görbe) képest.

A kettős exponenciális függvény egy konstans hatványát egy exponenciális függvény . Az általános képlet (ahol a > 1 és b > 1), amely sokkal gyorsabban növekszik, mint egy exponenciális függvény. Például, ha a = b = 10: ${\ displaystyle f (x) = a^{b^{x}} = a^{(b^{x})}}$

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

A faktorok gyorsabban nőnek, mint az exponenciális függvények, de sokkal lassabban, mint a kétszeresen exponenciális függvények. A tetráció és az Ackermann -funkció azonban gyorsabban nő. Lásd a Big O jelölést a különböző funkciók növekedési ütemének összehasonlításához.

A kettős exponenciális függvény fordítottja az ln (ln ( x )) kettős logaritmus .

Kétszeres exponenciális sorozatok

A pozitív egész számok (vagy valós számok) sorozatának kétszeres exponenciális növekedési üteme van, ha a szekvencia n -edik tagját megadó függvényt felül és alatt n kétszeresen exponenciális függvényei határolják . Ilyen például

• A Fermat számok
  $${\ displaystyle F (m) = 2^{2^{m}}+1}$$

  
• A harmonikus prímszámok: A p prímszámok , amelyekben az 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/ p szekvencia meghaladja a 0, 1, 2, 3,…
  Az első néhány szám 0 -tól kezdődően 2, 5, 277, 5195977, ... ( A016088 sorozat az OEIS -ben )
• A Double Mersenne számok
  $${\ displaystyle MM (p) = 2^{2^{p} -1} -1}$$

  
• Sylvester szekvenciájának elemei ( A000058 sorozat az OEIS -ben )
  $${\ displaystyle s_ {n} = \ left \ lfloor E^{2^{n+1}}+{\ frac {1} {2}} \ right \ rfloor}$$

  
  ahol E ≈ 1,264084735305302 a Vardi -állandó (az OEIS A076393 szekvenciája ).
• A k -ary logikai függvények száma :
  $${\ displaystyle 2^{2^{k}}}$$

  
• A prímszámok 2, 11, 1361, ... ( A051254 sorozat az OEIS -ben )
  $${\ displaystyle a (n) = \ left \ lfloor A^{3^{n}} \ right \ rfloor}$$

  
  ahol A ≈ 1,306377883863 Mills állandó .

Aho és Sloane megfigyelte, hogy számos fontos egész szekvenciában minden tag konstans plusz az előző tag négyzete. Azt mutatják, hogy az ilyen szekvenciákat úgy alakíthatjuk ki, hogy a középső kitevővel kétszeresen exponenciális függvény értékeit a legközelebbi egész számra kerekítjük. .

Alkalmazások

Algoritmus bonyolultsága

A számítási komplexitás elméletében néhány algoritmus kétszeres exponenciális időt vesz igénybe:

• A Presburger aritmetika minden döntési eljárása bizonyíthatóan legalább kétszer exponenciális időt igényel
• Gröbner -alap számítása egy területen. A legrosszabb esetben a Gröbner -bázis számos olyan elemet tartalmazhat, amelyek kétszeresen exponenciálisak a változók számában. Másrészt a Gröbner-alapú algoritmusok legrosszabb esetű összetettsége kétszeresen exponenciális a változók számában és a bejegyzés méretében is.
• Az asszociatív-kommutatív egységesítők teljes készletének megtalálása
• Megfelelő CTL ⁺ (ami valójában 2 EXPTIME teljes )
• A kvantorok kiküszöbölése a valódi zárt mezőkön kétszer exponenciális időt vesz igénybe (lásd: Hengeres algebrai felbontás ).
• Egy reguláris kifejezés kiegészítésének kiszámítása

Az algoritmusok tervezésének és elemzésének néhány más problémája során kétszer exponenciális sorozatokat használnak az algoritmus tervezésén belül, nem pedig annak elemzésekor. Példa erre Chan algoritmusa a domború hajótestek kiszámításához , amely egy számítási sorozatot hajt végre a h _i  = 2 ^{2 i} tesztértékek segítségével (becslés az esetleges kimeneti méretre), és a sorozat minden tesztértékéhez O ( n  log  h _i ) időt vesz igénybe. . Ezen tesztértékek kétszeres exponenciális növekedése miatt a szekvencia minden számításának ideje egyenként exponenciálisan nő az i függvényében , és a teljes időt a szekvencia utolsó lépésének ideje határozza meg. Így az algoritmus teljes ideje O ( n  log  h ), ahol h a tényleges kimeneti méret.

Számelmélet

Néhány számelméleti határ kettős exponenciális. Páratlan tökéletes számok az n különböző elsődleges tényezők ismert, hogy legfeljebb

${\ displaystyle 2^{4^{n}}}$

Nielsen (2003) eredménye. A k ≥ 1 belső rácsponttal rendelkező d -rácsos politóp maximális térfogata legfeljebb

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

Pikhurko eredménye.

Az elektronikus korszak legnagyobb ismert prímszáma nagyjából az év kétszeres exponenciális függvényeként nőtt, amióta Miller és Wheeler 79 számjegyű prímet talált az EDSAC 1-en 1951-ben.

Elméleti biológia

A népesség dinamikájában az emberi populáció növekedését néha kétszeres exponenciálisnak kell feltételezni. Varfolomejev és Gurevics kísérletileg illeszkedik

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

ahol N ( y ) az y év lakossága millióban .

Fizika

Az ön-pulzálás Toda oszcillátor modelljében az amplitúdó logaritmusa exponenciálisan változik az idővel (nagy amplitúdók esetén), így az amplitúdó az idő kétszeres exponenciális függvényeként változik.

Megfigyelték, hogy a dendritikus makromolekulák kétszeres exponenciális növekedést mutatnak.

Hivatkozások