Função exponencial dupla - Double exponential function

Uma função exponencial dupla (curva vermelha) em comparação com uma função exponencial única (curva azul).

Uma função exponencial dupla é uma constante elevada à potência de uma função exponencial . A fórmula geral é (onde a > 1 e b > 1), que cresce muito mais rapidamente do que uma função exponencial. Por exemplo, se 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 .

Os fatoriais crescem mais rápido do que as funções exponenciais, mas muito mais lentamente do que as funções duplamente exponenciais. No entanto, a tetração e a função de Ackermann crescem mais rápido. Consulte a notação Big O para uma comparação da taxa de crescimento de várias funções.

O inverso da função exponencial dupla é o logaritmo duplo ln (ln ( x )).

Sequências duplamente exponenciais

Diz-se que uma sequência de inteiros positivos (ou números reais) tem taxa de crescimento duplamente exponencial se a função que dá o n- ésimo termo da sequência for limitada acima e abaixo por funções duplamente exponenciais de n . Exemplos incluem

• Os números de Fermat
  $${\ displaystyle F (m) = 2 ^ {2 ^ {m}} + 1}$$

  
• Os primos harmônicos: Os primos p , em que a sequência 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1 / p excede 0, 1, 2, 3, ...
  Os primeiros números, começando com 0, são 2, 5, 277, 5195977, ... (sequência A016088 no OEIS )
• Os números da Double Mersenne
  $${\ displaystyle MM (p) = 2 ^ {2 ^ {p} -1} -1}$$

  
• Os elementos da sequência de Sylvester (sequência A000058 no OEIS )
  $${\ displaystyle s_ {n} = \ left \ lfloor E ^ {2 ^ {n + 1}} + {\ frac {1} {2}} \ right \ rfloor}$$

  
  onde E ≈ 1,264084735305302 é a constante de Vardi (sequência A076393 no OEIS ).
• O número de funções booleanas k -ary :
  $${\ displaystyle 2 ^ {2 ^ {k}}}$$

  
• Os números primos 2, 11, 1361, ... (sequência A051254 no OEIS )
  $${\ displaystyle a (n) = \ left \ lfloor A ^ {3 ^ {n}} \ right \ rfloor}$$

  
  onde A ≈ 1.306377883863 é a constante de Mills .

Aho e Sloane observaram que em várias sequências inteiras importantes , cada termo é uma constante mais o quadrado do termo anterior. Eles mostram que tais sequências podem ser formadas arredondando para o inteiro mais próximo os valores de uma função duplamente exponencial com o expoente médio 2. Ionaşcu e Stănică descrevem algumas condições mais gerais suficientes para uma sequência ser o piso de uma sequência duplamente exponencial mais uma constante .

Formulários

Complexidade algorítmica

Na teoria da complexidade computacional , alguns algoritmos levam um tempo duplamente exponencial:

• Cada procedimento de decisão para aritmética Presburger provavelmente requer pelo menos um tempo duplamente exponencial
• Calculando uma base de Gröbner sobre um campo. No pior caso, uma base de Gröbner pode ter um número de elementos que é duplamente exponencial no número de variáveis. Por outro lado, a complexidade de pior caso dos algoritmos de base de Gröbner é duplamente exponencial no número de variáveis, bem como no tamanho da entrada.
• Encontrar um conjunto completo de unificadores associativo-comutativo
• Satisfazendo CTL ⁺ (que é, na verdade, 2-EXPTIME -completo)
• A eliminação do quantificador em campos fechados reais leva um tempo duplamente exponencial (ver decomposição algébrica cilíndrica ).
• Calculando o complemento de uma expressão regular

Em alguns outros problemas no projeto e análise de algoritmos, sequências duplamente exponenciais são usadas no projeto de um algoritmo, e não em sua análise. Um exemplo é o algoritmo de Chan para calcular cascos convexos , que realiza uma sequência de cálculos usando valores de teste h _i  = 2 ^{2 i} (estimativas para o tamanho de saída eventual), levando o tempo O ( n  log  h _i ) para cada valor de teste na sequência . Por causa do crescimento exponencial duplo desses valores de teste, o tempo para cada cálculo na sequência cresce exponencialmente em função de i , e o tempo total é dominado pelo tempo para a etapa final da sequência. Assim, o tempo total para o algoritmo é O ( n  log  h ), onde h é o tamanho real da saída.

Teoria dos Números

Alguns limites teóricos numéricos são duplamente exponenciais. Números perfeitos ímpares com n fatores primos distintos são conhecidos por serem no máximo

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

um resultado de Nielsen (2003). O volume máximo de um politopo de rede d com k ≥ 1 pontos de rede interior é no máximo

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

um resultado de Pikhurko.

O maior número primo conhecido na era eletrônica cresceu aproximadamente como uma função exponencial dupla do ano desde que Miller e Wheeler encontraram um primo de 79 dígitos no EDSAC 1 em 1951.

Biologia teórica

Na dinâmica populacional, às vezes supõe-se que o crescimento da população humana seja duplamente exponencial. Varfolomeyev e Gurevich se ajustaram experimentalmente

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

onde N ( y ) é a população em milhões no ano y .

Física

No oscilador Toda modelo de auto-pulsação , o logaritmo da amplitude varia exponencialmente com o tempo (para grandes amplitudes), portanto, a amplitude varia em função duplamente exponencial de tempo.

Observou-se que macromoléculas dendríticas crescem de forma duplamente exponencial.

Referências