Em matemática, a busca por fórmulas exatas que forneçam todos os números primos, certas famílias de números primos ou o n- ésimo número primo geralmente provou ser em vão, o que levou a ficar satisfeito com fórmulas aproximadas. Esta página lista os principais resultados obtidos.
A esperança de obter uma fórmula exata e simples dando o n - ésimo número primo p n , ou o número π ( n ) de números primos menor ou igual a n , muito cedo encontrou a extrema irregularidade de sua distribuição , o que levou ao conteúdo com metas menos ambiciosas. Mas mesmo a busca por fórmulas que fornecem apenas números primos acaba sendo bastante decepcionante; assim, é fácil mostrar que não há função polinomial não constante P ( n ) que tomaria apenas os primeiros valores para todos os inteiros n , ou mesmo quase todos os n ; na verdade, nem mesmo sabemos se existe um polinômio de grau> 1 que assume uma infinidade de valores primos.
Isso explica o interesse da observação de Euler : o polinômio quadrático P ( n ) = n 2 + n + 41 é primo para todos os inteiros positivos estritamente menores que 40 (observe que e se n for um múltiplo de 41, P ( n ) também ser um múltiplo de 41 e, portanto, não primo). Além disso, 41 é o maior “ número de Euler da sorte ”, ou seja, o maior inteiro A para o qual o polinômio n 2 + n + A é primo para todo n estritamente menor que A - 1 ; isso segue do teorema de Stark-Heegner , um resultado da teoria do campo de classe que não foi demonstrada até 1967. Da mesma forma, outras fórmulas polinomiais (grau superior) produzem sequências de números primos. Assim, em 2010, um deles permitiu estabelecer um novo recorde: uma sequência de 58 números primos:
é primo para cada inteiro n de –42 a 15.Outras fórmulas usando funções mais gerais, como a de Mersenne , foram consideradas, a mais famosa sendo aquela conjecturada por Fermat : F n = 2 2 n + 1 é primo para todo n . Infelizmente, se esses números (doravante chamados de números de Fermat ) são de fato primos para 0 ≤ n ≤ 4 , Euler descobriu que o sexto, F 5 , é divisível por 641, arruinando a conjectura; atualmente, pensamos, ao contrário, que F n é sempre composto tão logo n > 4 . Na mesma linha, a fórmula de Mills gera apenas números primos, mas tem a desvantagem de ser apenas teórica.
Fórmulas aproximadas para p n ou π ( n ) foram concebidas para XVIII th século, culminando com a conjectura de Legendre e Gauss . Se sua hipótese mais simples foi demonstrada por Hadamard e La Vallée Poussin um século depois (é o teorema dos números primos ), a dificuldade do problema é bem demonstrada pelo fato de que uma das conjecturas de Gauss, mais precisa, e delimitadora π ( n ) by , que parecia muito plausível em vista das tabelas dessas duas funções , revelou-se, no entanto, falso, mas apenas para valores gigantescos de n .
Resultados mais precisos, e em particular uma boa estimativa do termo de erro h ( n ) na fórmula p n = n ln n + h ( n ) , ainda estão sujeitos a conjecturas (muitas vezes dependendo da suposição de Riemann ); entre os melhores resultados realmente demonstrados, podemos citar o seguinte referencial, determinado por Dusart em 1999:
Esses métodos estão longe de fornecer fórmulas exatas; por exemplo, este quadro afirma apenas que o milésimo número primo, 7919, está entre 7840 e 8341.
Apesar das observações anteriores, é possível obter fórmulas exatas de aparência simples, mas sem interesse prático por causa de cálculos muito longos.
O teorema de Wilson torna fácil mostrar que a função f ( n ) = 2 + (2 ( n ) mod (? N + 1)) produz todos os números primos, e somente eles, quando n passa por todos os inteiros positivos: f ( n ) = n + 1 se n + 1 for primo e f ( n ) = 2 caso contrário.
O fatorial de n rapidamente assume valores muito grandes para serem usados na prática, mas o uso da função módulo (que sabemos como calcular rapidamente) contorna essa dificuldade; entretanto, os únicos métodos conhecidos para calcular f ( n ) levam cerca de n operações elementares, além disso, esta função não fornece realmente π ( n ) , mas apenas testa se n é primo ou não; para este teste, ou para calcular π ( n ) , f é, portanto, muito mais ineficiente do que o método de divisão por todos os inteiros menores ou iguais a √ n (ou do que a peneira de Eratóstenes ), métodos eles próprios muito mais lentos do que os melhores atualmente testes de primalidade conhecidos.
Outras fórmulas que fornecem diretamente p n ou π ( n ) podem ser construídas a partir de f ; assim, temos, usando a função inteira ⌊ ∙ ⌋ :
;mas essas fórmulas são ainda menos fáceis de usar do que aquela que fornece f .
Outra abordagem, mais promissora e não usando o teorema de Wilson, consiste essencialmente em simular a peneira de Eratóstenes , ou as fórmulas que dela podem ser deduzidas, como a fórmula de inclusão-exclusão de Legendre; é o terreno preferido de muitos amadores, portanto, as seguintes fórmulas foram determinadas em 2000 por um professor de espanhol, SM Ruiz:
e
Observe o grande número de somas nessas fórmulas, o que significa que elas também não seriam muito úteis na prática; métodos muito melhores de cálculo exato de π ( n ) e p n , que encontraremos detalhados no artigo dedicado a essas funções , permanecem relativamente ineficientes.
Levando em consideração as observações da primeira seção, a existência de polinômios com várias variáveis tomando apenas valores primos parecia improvável. Além disso, o trabalho de Matiyasevich que resolveu em 1970 o décimo problema de Hilbert , mostrando que qualquer relação diofantina poderia ser codificada por tal polinômio, causou uma verdadeira surpresa. É até possível dar exemplos explícitos desse resultado; assim, o seguinte polinômio monstruoso (de grau 25 e compreendendo 26 variáveis):
com
a, para um conjunto de valores estritamente positivos (quando ), exatamente o conjunto de números primos.
Mas pode-se questionar se realmente está aqui novamente de uma "fórmula". Também é extremamente difícil encontrar um conjunto de 26 variáveis que forneçam um número positivo, e não há nenhum método conhecido para resolver tal sistema a não ser explorar todas as combinações possíveis dos parâmetros.
Embora não possamos falar exatamente de uma fórmula, uma sequência definida por uma relação da forma u n +1 = f ( u n ) , onde f é uma função bastante simples, e que assumiria apenas valores primos, permaneceria interessante. Certas sequências derivadas da prova de Euclides da infinidade de números primos ( como a sequência de Sylvester ) revelaram -se decepcionantes a esse respeito, de modo que nem mesmo sabemos se existe uma infinidade de primos primitivos . Na verdade, conhecemos apenas alguns exemplos interessantes de tais sequências, além disso, de uma forma um pouco mais complexa.
Algoritmo FRACTRANConway assim definiu uma generalização do problema de Syracuse , que o transforma em uma linguagem de programação, FRACTRAN ; o seguinte texto:
corresponde, para esta linguagem, a um programa que produz, por ordem, a sequência de números primos (podemos portanto interpretá-la como uma sequência definida por indução); sendo a eficácia deste programa extremamente fraca, o interesse está apenas na elegância de sua escrita.
Suite RowlandA sequência u n definida pela relação de recorrência
(onde mdc ( x , y ) denota o GCD de x e y ) e u n = a n +1 - a n começa com 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3 , 1, 1, ... (continuação A132199 do OEIS ). Rowland demonstrou em 2008 que essa sequência contém (exceto 1) apenas números primos.
Sequências dependendo de um número real Fórmula de moinhosEm 1947, William H. Mills mostrou que existem números reais M tais que, para qualquer inteiro n , a parte inteira de M (3 n ) é um número primo. O menor M com essa propriedade, a constante de Mills , também é conhecido com boa precisão, mas que acaba sendo igualmente ilusório para calcular grandes números primos, por exemplo, porque o tamanho de p ( n ) = ⌊ M (3 n ) ⌋ rapidamente se torna muito maior do que qualquer coisa que um computador pode conter (para armazenar p (25) , você já precisa de um terabyte ).
Suite FridmanEm 2017, Fridman et al. mostraram que a sequência de reais ( f n ) definida por:
verificado:
.O irracional f 1 = 2,9200509773 ... não é outro senão o valor médio da sequência 2, 3, 2, 3, 2, 5, etc. cujo n- ésimo termo é o menor número primo que não divide n .
Embora os cálculos correspondentes sejam mais gerenciáveis do que os da fórmula de Mills, esse resultado permanece tão teórico quanto. Na verdade, esses cálculos requerem o conhecimento de um número crescente de decimais de f 1 (aproximadamente n decimais para obter p n ) , mas para obter n decimais de f 1 , já devemos saber os valores dos primeiros n números primos . Por outro lado, isso fornece compactação de memória , de fato, o armazenamento de decimais requer menos memória do que para os primeiros números primos.
Fração contínuaO conceito de fração contínua usado para definir o número real positivo A064442 a partir do qual encontramos a seqüência de números primos, utilizando a seguinte recorrência: . Segue isso .
O método de Fridman et al. pode ser visto como uma alternativa ao método da fração contínua (conhecido anteriormente) e, portanto, podemos fazer a mesma reserva: o número é definido (acima) usando números primos, portanto, precisamos primeiro de uma definição alternativa independente dos números para este método ser utilizável .
(en) Eric W. Weisstein , “ Prime Formulas ” , no MathWorld