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

Двойная экспоненциальная функция (красная кривая) в сравнении с одинарной экспоненциальной функцией (синяя кривая).

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

• ж (х) = 10 ^{10 х}
• ж (0) = 10
• ж (1) = 10 ¹⁰
• ж (2) = 10 ¹⁰⁰ = вырезать
• ж (3) = 10 ¹⁰⁰⁰
• ж (100) = 10 ^{10 100} = Гуголплекс .

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

Обратная двойная экспоненциальная функция — это двойной логарифм log(log( x )).

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

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

• Ферма Числа
  $$F(m)=2^{2^{m}}+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 )
  $$s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor$$
  где E ≈ 1,264084735305302 — константа Варди (последовательность A076393 в OEIS ).
• Количество k -арных булевых функций :
  $$2^{2^{k}}$$
• Простые числа 2, 11, 1361, ... (последовательность A051254 в OEIS )
  $$a(n)=\left\lfloor A^{3^{n}}\right\rfloor$$
  где A ≈ 1,306377883863 — постоянная Миллса .

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

Приложения

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

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

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

Теория чисел

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

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

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

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

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

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

В демографической динамике иногда предполагается, что рост численности населения имеет двойную экспоненциальную зависимость. Варфоломеев и Гуревич экспериментально подходит

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

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

Физика

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

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