Двойная показательная функция

Двойная показательная функция — это константа , возведенная в степень показательной функции . Общая формула имеет вид (где a >1 и b >1), которая растет гораздо быстрее показательной функции. Например, если a = b = 10: $f(x)=a^{b^{x}}=a^{(b^{x})}$

f (х) = 10 ^{10 ^х}
ф (0) = 10
ф (1) = 10 ¹⁰
f (2) = 10 ¹⁰⁰ = гугол
ф (3) = 10 ¹⁰⁰⁰
f (100) = 10 ^{10 ¹⁰⁰} = гуголплекс .

Факториалы растут быстрее, чем показательные функции, но гораздо медленнее, чем двойные показательные функции. Однако тетрация и функция Аккермана растут быстрее. См. нотацию Big O для сравнения скорости роста различных функций.

Обратная функция двойной показательной функции — двойной логарифм log(log( x )). Сложная двойная показательная функция является целой , поскольку она представляет собой композицию двух целых функций и . $f(x)=a^{x}=e^{x\ln a}$ $g(x)=b^{x}=e^{x\ln b}$

Двойные экспоненциальные последовательности

Говорят, что последовательность положительных целых чисел (или действительных чисел) имеет двойную экспоненциальную скорость роста , если функция, задающая $n$ -й член последовательности, ограничена сверху и снизу двойными экспоненциальными функциями от $n$ . Примеры включают

Числа Ферма $F(м)=2^{2^{м}}+1$
Гармонические простые числа: Простые числа p , в которых последовательность 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/ p превышает 0, 1, 2, 3, …
Первые несколько чисел, начиная с 0, это 2, 5, 277, 5195977, ... (последовательность A016088 в OEIS )
Двойные числа Мерсенна $MM(p)=2^{2^{p}-1}-1$
Элементы последовательности Сильвестра (последовательность A000058 в OEIS ) , где E ≈ 1,264084735305302 — константа Варди (последовательность A076393 в OEIS ). $s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor$
Число k -ичных булевых функций : $2^{2^{k}}$
Простые числа 2, 11, 1361, ... (последовательность A051254 в OEIS ) , где A ≈ 1,306377883863 — постоянная Миллса . $a(n)=\left\lfloor A^{3^{n}}\right\rfloor$

Ахо и Слоан заметили, что в нескольких важных целочисленных последовательностях каждый член является константой плюс квадрат предыдущего члена. Они показывают, что такие последовательности могут быть сформированы путем округления до ближайшего целого значения двойной экспоненциальной функции со средним показателем 2. ^[1] Ионашку и Станица описывают некоторые более общие достаточные условия для того, чтобы последовательность была полом двойной экспоненциальной последовательности плюс константа. ^[2]

Приложения

Алгоритмическая сложность

В теории вычислительной сложности 2-EXPTIME — это класс задач принятия решений, решаемых за двойное экспоненциальное время. Он эквивалентен AEXPSPACE, множеству задач принятия решений, решаемых чередующейся машиной Тьюринга в экспоненциальном пространстве, и является надмножеством EXPSPACE . ^[3] Примером задачи из 2-EXPTIME, которая не находится в EXPTIME, является задача доказательства или опровержения утверждений в арифметике Пресбургера . ^[4]

В некоторых других задачах проектирования и анализа алгоритмов двойные экспоненциальные последовательности используются в проектировании алгоритма, а не в его анализе. Примером является алгоритм Чана для вычисления выпуклых оболочек , который выполняет последовательность вычислений с использованием тестовых значений h _i = 2 ^{2 ⁱ} (оценки для конечного размера вывода), затрачивая время O( n log h _i ) на каждое тестовое значение в последовательности. Из-за двойного экспоненциального роста этих тестовых значений время каждого вычисления в последовательности растет одинарно экспоненциально как функция i , и общее время определяется временем для последнего шага последовательности. Таким образом, общее время для алгоритма составляет O( n log h ), где h — фактический размер вывода. ^[5]

Теория чисел

Некоторые теоретические границы чисел являются дважды экспоненциальными. Известно, что нечетные совершенные числа с n различными простыми множителями не превышают , результат Нильсена (2003). ^[6] $2^{4^{n}}$

Максимальный объем многогранника в d - мерной целочисленной решетке с k ≥ 1 внутренними точками решетки не превышает

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

результат Пихурко (2001). ^[7]

Наибольшее известное простое число в электронную эпоху росло примерно как двойная экспоненциальная функция года с тех пор, как Миллер и Уиллер нашли 79-значное простое число на EDSAC 1 в 1951 году. ^[8]

Теоретическая биология

В популяционной динамике рост человеческой популяции иногда предполагается дважды экспоненциальным. Варфоломеев и Гуревич ^[9] экспериментально подобрали

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

где N ( y ) — численность населения в миллионах человек в году y .

Физика

В модели самопульсации осциллятора Тоды логарифм амплитуды изменяется экспоненциально со временем (для больших амплитуд), таким образом, амплитуда изменяется как двойная экспоненциальная функция времени. ^[10]

Было обнаружено, что дендритные макромолекулы растут в двойной экспоненциальной зависимости. ^[11]

Ссылки

^ Ахо, AV ; Слоан, NJA (1973), «Некоторые дважды экспоненциальные последовательности», Fibonacci Quarterly , 11 : 429–437.
^ Ионашку, Ожен-Жюльен; Станица, Пантелимон (2004), «Эффективная асимптотика для некоторых нелинейных повторений и почти двукратно-экспоненциальных последовательностей» (PDF) , Acta Mathematica Universitatis Comenianae , LXXIII (1): 75–87.
^ Христос Пападимитриу , Вычислительная сложность (1994), ISBN 978-0-201-53082-7 . Раздел 20.1, следствие 3, стр. 495.
^ Фишер, М. Дж . и Майкл О. Рабин , 1974, ""Суперэкспоненциальная сложность арифметики Пресбургера. Архивировано 15 сентября 2006 г. в Wayback Machine " Труды симпозиума SIAM-AMS по прикладной математике, том 7 : 27–41
^ Чан, ТМ (1996), «Оптимальные алгоритмы выпуклой оболочки, чувствительные к выходу, в двух и трех измерениях», Дискретная и вычислительная геометрия , 16 (4): 361–368, doi : 10.1007/BF02712873 , MR 1414961
^ Нильсен, Пейс П. (2003), «Верхняя граница для нечетных совершенных чисел», ЦЕЛЫЕ ЧИСЛА: Электронный журнал комбинаторной теории чисел , 3 : A14.
^ Пихурко, Олег (2001), "Точки решетки в решетчатых многогранниках", Mathematika , 48 (1–2): 15–24, arXiv : math/0008028 , Bibcode : 2000math......8028P, doi : 10.1112/s0025579300014339
^ Миллер, JCP; Уилер, DJ (1951), "Большие простые числа", Nature , 168 (4280): 838, Bibcode : 1951Natur.168..838M, doi : 10.1038/168838b0.
^ Варфоломеев, С.Д.; Гуревич, К.Г. (2001), «Гиперэкспоненциальный рост человеческой популяции в макроисторическом масштабе», Журнал теоретической биологии , 212 (3): 367–372, Bibcode : 2001JThBi.212..367V, doi : 10.1006/jtbi.2001.2384, PMID 11829357.
^ Кузнецов, Д.; Биссон, Ж.-Ф.; Ли, Дж.; Уэда, К. (2007), «Самопульсирующий лазер как осциллятор Тоды: приближение через элементарные функции», Журнал физики 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 .
^ Кавагучи, Тору; Уокер, Кэтлин Л.; Уилкинс, Чарльз Л.; Мур, Джеффри С. (1995). «Двойной экспоненциальный рост дендримера». Журнал Американского химического общества . 117 (8): 2159–2165. doi :10.1021/ja00113a005.