Fórmula para primos - Formula for primes

Na teoria dos números , uma fórmula para primos é uma fórmula que gera os números primos , exatamente e sem exceção. Nenhuma fórmula que seja eficientemente computável é conhecida. Uma série de restrições são conhecidas, mostrando o que essa "fórmula" pode e não pode ser.

Fórmulas baseadas no teorema de Wilson

Uma fórmula simples é

${\ displaystyle f (n) = \ left \ lfloor {\ frac {n! {\ bmod {(}} n + 1)} {n}} \ right \ rfloor (n-1) +2}$

para número inteiro positivo , onde é a função de piso , que é arredondada para o número inteiro mais próximo. Pelo teorema de Wilson , é primo se e somente se . Assim, quando é primo, o primeiro fator no produto torna-se um e a fórmula produz o número primo . Mas quando não é primo, o primeiro fator torna-se zero e a fórmula produz o número primo 2. Esta fórmula não é uma maneira eficiente de gerar números primos porque a avaliação requer multiplicações e reduções do módulo . ${\ displaystyle n}$${\ displaystyle \ lfloor \ \ rfloor}$${\ displaystyle n + 1}$${\ displaystyle n! \ equiv n {\ pmod {n + 1}}}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ displaystyle n! {\ bmod {(}} n + 1)}$${\ displaystyle n-1}$${\ displaystyle n + 1}$

Em 1964, Willans deu a fórmula

${\ displaystyle p_ {n} = 1 + \ sum _ {i = 1} ^ {2 ^ {n}} \ left \ lfloor \ left ({\ frac {n} {\ sum _ {j = 1} ^ { i} \ left \ lfloor \ left (\ cos {\ frac {(j-1)! + 1} {j}} \ pi \ right) ^ {2} \ right \ rfloor}} \ right) ^ {1 / n} \ right \ rfloor}$

para o º número primo . Esta fórmula também não é eficiente. Além da aparência de , ele calcula adicionando cópias de ; por exemplo ,. ${\ displaystyle n}$${\ displaystyle p_ {n}}$${\ displaystyle (j-1)!}$${\ displaystyle p_ {n}}$${\ displaystyle p_ {n}}$${\ displaystyle 1}$${\ displaystyle p_ {5} = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 0 + 0 + \ dots + 0 = 11}$

Fórmula baseada em um sistema de equações diofantinas

Como o conjunto de primos é um conjunto computavelmente enumerável , pelo teorema de Matiyasevich , ele pode ser obtido a partir de um sistema de equações diofantinas . Jones et al. (1976) encontraram um conjunto explícito de 14 equações diofantinas em 26 variáveis, de modo que um determinado número k  + 2 é primo se e somente se esse sistema tiver uma solução em números naturais :

${\ displaystyle \ alpha _ {0} = wz + h + jq = 0}$

${\ displaystyle \ alpha _ {1} = (gk + 2g + k + 1) (h + j) + hz = 0}$

${\ displaystyle \ alpha _ {2} = 16 (k + 1) ^ {3} (k + 2) (n + 1) ^ {2} + 1-f ^ {2} = 0}$

${\ displaystyle \ alpha _ {3} = 2n + p + q + ze = 0}$

${\ displaystyle \ alpha _ {4} = e ^ {3} (e + 2) (a + 1) ^ {2} + 1-o ^ {2} = 0}$

${\ displaystyle \ alpha _ {5} = (a ^ {2} -1) y ^ {2} + 1-x ^ {2} = 0}$

${\ displaystyle \ alpha _ {6} = 16r ^ {2} y ^ {4} (a ^ {2} -1) + 1-u ^ {2} = 0}$

${\ displaystyle \ alpha _ {7} = n + \ ell + vy = 0}$

${\ displaystyle \ alpha _ {8} = (a ^ {2} -1) \ ell ^ {2} + 1-m ^ {2} = 0}$

${\ displaystyle \ alpha _ {9} = ai + k + 1- \ ell -i = 0}$

${\ displaystyle \ alpha _ {10} = ((a + u ^ {2} (u ^ {2} -a)) ^ {2} -1) (n + 4dy) ^ {2} + 1- (x + cu) ^ {2} = 0}$

${\ displaystyle \ alpha _ {11} = p + \ ell (an-1) + b (2an + 2a-n ^ {2} -2n-2) -m = 0}$

${\ displaystyle \ alpha _ {12} = q + y (ap-1) + s (2ap + 2a-p ^ {2} -2p-2) -x = 0}$

${\ displaystyle \ alpha _ {13} = z + p \ ell (ap) + t (2ap-p ^ {2} -1) -pm = 0}$

As 14 equações α ₀ , ..., α ₁₃ podem ser usadas para produzir uma desigualdade polinomial de geração de prime em 26 variáveis:

${\ displaystyle (k + 2) (1- \ alpha _ {0} ^ {2} - \ alpha _ {1} ^ {2} - \ cdots - \ alpha _ {13} ^ {2})> 0}$

ie:

${\ displaystyle {\ begin {alinhados} & (k + 2) (1 - {} \\ [6pt] & [wz + h + jq] ^ {2} - {} \\ [6pt] & [(gk + 2g + k + 1) (h + j) + hz] ^ {2} - {} \\ [6pt] & [16 (k + 1) ^ {3} (k + 2) (n + 1) ^ { 2} + 1-f ^ {2}] ^ {2} - {} \\ [6pt] & [2n + p + q + ze] ^ {2} - {} \\ [6pt] & [e ^ { 3} (e + 2) (a + 1) ^ {2} + 1-o ^ {2}] ^ {2} - {} \\ [6pt] & [(a ^ {2} -1) y ^ {2} + 1-x ^ {2}] ^ {2} - {} \\ [6pt] & [16r ^ {2} y ^ {4} (a ^ {2} -1) + 1-u ^ {2}] ^ {2} - {} \\ [6pt] & [n + \ ell + vy] ^ {2} - {} \\ [6pt] & [(a ^ {2} -1) \ ell ^ {2} + 1-m ^ {2}] ^ {2} - {} \\ [6pt] & [ai + k + 1- \ ell -i] ^ {2} - {} \\ [6pt] & [((a + u ^ {2} (u ^ {2} -a)) ^ {2} -1) (n + 4dy) ^ {2} + 1- (x + cu) ^ {2}] ^ {2} - {} \\ [6pt] & [p + \ ell (an-1) + b (2an + 2a-n ^ {2} -2n-2) -m] ^ {2} - {} \\ [6pt] & [q + y (ap-1) + s (2ap + 2a-p ^ {2} -2p-2) -x] ^ {2} - {} \\ [6pt] & [z + p \ ell (ap) + t (2ap-p ^ {2} -1) -pm] ^ {2}) \\ [6pt] &> 0 \ end {alinhado}}}$

é uma desigualdade polinomial em 26 variáveis, e o conjunto de números primos é idêntico ao conjunto de valores positivos assumidos pelo lado esquerdo, pois as variáveis a , b , ..., z variam sobre os inteiros não negativos.

Um teorema geral de Matiyasevich diz que se um conjunto é definido por um sistema de equações diofantinas, ele também pode ser definido por um sistema de equações diofantinas em apenas 9 variáveis. Conseqüentemente, há um polinômio gerador de primos como acima com apenas 10 variáveis. No entanto, seu grau é grande (na ordem de 10 ⁴⁵ ). Por outro lado, também existe tal conjunto de equações de grau apenas 4, mas em 58 variáveis.

Fórmula de Mills

A primeira fórmula conhecida foi estabelecida por WH Mills ( 1947 ), que provou que existe um número real A tal que, se

${\ displaystyle d_ {n} = A ^ {3 ^ {n}}}$

então

${\ displaystyle \ left \ lfloor d_ {n} \ right \ rfloor = \ left \ lfloor A ^ {3 ^ {n}} \ right \ rfloor}$

é um número primo para todos os inteiros positivos n . Se a hipótese de Riemann for verdadeira, então o menor A tem um valor de cerca de 1,3063778838630806904686144926 ... (sequência A051021 no OEIS ) e é conhecido como constante de Mills . Este valor dá origem aos primos , , , ... (seqüência A051254 no OEIS ). Muito pouco se sabe sobre a constante A (nem mesmo se é racional ). Essa fórmula não tem valor prático, porque não há maneira conhecida de calcular a constante sem encontrar os primos em primeiro lugar. ${\ displaystyle \ left \ lfloor d_ {1} \ right \ rfloor = 2}$${\ displaystyle \ left \ lfloor d_ {2} \ right \ rfloor = 11}$${\ displaystyle \ left \ lfloor d_ {3} \ right \ rfloor = 1361}$

Observe que não há nada de especial sobre a função floor na fórmula. Tóth provou que também existe uma constante tal que ${\ displaystyle B}$

${\ displaystyle \ lceil B ^ {r ^ {n}} \ rceil}$

também é o principal representante para ( Tóth 2017 ). ${\ displaystyle r> 2.106 \ ldots}$

Nesse caso , o valor da constante começa com 1.24055470525201424067 ... Os primeiros primos gerados são: ${\ displaystyle r = 3}$${\ displaystyle B}$

${\ displaystyle 2,7,337,38272739,56062005704198360319209,176199995814327287356671209104585864397055039072110696028654438846269, \ ldots}$

Sem assumir a hipótese de Riemann, Elsholtz desenvolveu várias funções de representação de primos semelhantes às de Mills. Por exemplo, se , então é primo para todos os inteiros positivos . Da mesma forma, se , então, é primo para todos os inteiros positivos . ${\ displaystyle A \ approx 1.00536773279814724017}$${\ displaystyle \ left \ lfloor A ^ {10 ^ {10n}} \ right \ rfloor}$${\ displaystyle n}$${\ displaystyle A \ approx 3.8249998073439146171615551375}$${\ displaystyle \ left \ lfloor A ^ {3 ^ {13n}} \ right \ rfloor}$${\ displaystyle n}$

Fórmula de Wright

Outra fórmula geradora de primos semelhante à de Mills vem de um teorema de EM Wright . Ele provou que existe um número real α tal que, se

${\ displaystyle g_ {0} = \ alpha}$ e

${\ displaystyle g_ {n + 1} = 2 ^ {g_ {n}}}$para ,${\ displaystyle n \ geq 0}$

então

${\ displaystyle \ left \ lfloor g_ {n} \ right \ rfloor = \ left \ lfloor 2 ^ {\ dots ^ {2 ^ {2 ^ {\ alpha}}}} \ right \ rfloor}$

é excelente para todos . Wright dá os primeiros sete casas decimais de tal constante a: . Este valor dá origem aos primos , e . é par e, portanto, não é primo. No entanto, com , , , e mantêm-se inalterados, enquanto é primo com 4932 dígitos. Esta sequência de primos não pode ser estendida além sem conhecer mais dígitos de . Como a fórmula de Mills, e pelas mesmas razões, a fórmula de Wright não pode ser usada para encontrar primos. ${\ displaystyle n \ geq 1}$${\ displaystyle \ alpha = 1.9287800}$${\ displaystyle \ left \ lfloor g_ {1} \ right \ rfloor = \ left \ lfloor 2 ^ {\ alpha} \ right \ rfloor = 3}$${\ displaystyle \ left \ lfloor g_ {2} \ right \ rfloor = 13}$${\ displaystyle \ left \ lfloor g_ {3} \ right \ rfloor = 16381}$${\ displaystyle \ left \ lfloor g_ {4} \ right \ rfloor}$${\ displaystyle \ alpha = 1,9287800 + 8,2843 \ cdot 10 ^ {- 4933}}$${\ displaystyle \ left \ lfloor g_ {1} \ right \ rfloor}$${\ displaystyle \ left \ lfloor g_ {2} \ right \ rfloor}$${\ displaystyle \ left \ lfloor g_ {3} \ right \ rfloor}$${\ displaystyle \ left \ lfloor g_ {4} \ right \ rfloor}$${\ displaystyle \ left \ lfloor g_ {4} \ right \ rfloor}$${\ displaystyle \ alpha}$

Uma função que representa todos os primos

Dada a constante (sequência A249270 no OEIS ), para definir a sequência ${\ displaystyle f_ {1} = 2,920050977316 \ ldots}$${\ displaystyle n \ geq 2}$

${\ displaystyle f_ {n} = \ left \ lfloor f_ {n-1} \ right \ rfloor (f_ {n-1} - \ left \ lfloor f_ {n-1} \ right \ rfloor +1)}$

( 1 )

onde fica a função chão . Em seguida, para , iguala o th privilegiada: , , , etc. A constante inicial dada no artigo é suficientemente preciso para a equação ( 1 ) para gerar os números primos através de 37, o th privilegiada. ${\ displaystyle \ left \ lfloor \ \ right \ rfloor}$${\ displaystyle n \ geq 1}$${\ displaystyle \ left \ lfloor f_ {n} \ right \ rfloor}$${\ displaystyle n}$${\ displaystyle \ left \ lfloor f_ {1} \ right \ rfloor = 2}$${\ displaystyle \ left \ lfloor f_ {2} \ right \ rfloor = 3}$${\ displaystyle \ left \ lfloor f_ {3} \ right \ rfloor = 5}$${\ displaystyle f_ {1} = 2,920050977316}$${\ displaystyle 12}$

O valor exato de que gera todos os primos é dado pela série de convergência rápida${\ displaystyle f_ {1}}$

${\ displaystyle f_ {1} = \ sum _ {n = 1} ^ {\ infty} {\ frac {p_ {n} -1} {P_ {n}}} = {\ frac {2-1} {1 }} + {\ frac {3-1} {2}} + {\ frac {5-1} {2 \ cdot 3}} + {\ frac {7-1} {2 \ cdot 3 \ cdot 5}} + \ cdots,}$

onde é o ésimo primo, e o produto de todos os primos é menor que . Quanto mais dígitos soubermos, mais primos a equação ( 1 ) gerará. Por exemplo, podemos usar 25 termos na série, usando os 25 primos menores que 100, para calcular a seguinte aproximação mais precisa: ${\ displaystyle p_ {n}}$${\ displaystyle n}$${\ displaystyle P_ {n}}$${\ displaystyle p_ {n}}$${\ displaystyle f_ {1}}$

${\ displaystyle f_ {1} \ simeq 2.920050977316134712092562917112019.}$

Isso tem dígitos suficientes para a equação ( 1 ) para render novamente os 25 primos menores que 100.

Tal como acontece com a fórmula de Mills e a fórmula de Wright acima, para gerar uma lista mais longa de primos, precisamos começar sabendo mais dígitos da constante inicial , o que, neste caso, requer uma lista mais longa de primos em seu cálculo. ${\ displaystyle f_ {1}}$

Fórmulas de Plouffe

Em 2018, Simon Plouffe conjecturou um conjunto de fórmulas para os primos. Da mesma forma que a fórmula de Mills, eles são da forma

${\ displaystyle \ left \ {a_ {0} ^ {r ^ {n}} \ right \}}$

onde é a função arredondando para o inteiro mais próximo. Por exemplo, com e , isso dá 113, 367, 1607, 10177, 102217 ... Usando e com um certo número entre 0 e meio, Plouffe descobriu que poderia gerar uma sequência de 50 primos prováveis (com alta probabilidade de ser melhor). Presumivelmente, existe um ε tal que esta fórmula dará uma sequência infinita de números primos reais. O número de dígitos começa em 501 e aumenta cerca de 1% a cada vez. ${\ displaystyle \ {\ \}}$${\ displaystyle a_ {0} \ approx 43.80468771580293481}$${\ displaystyle r = 5/4}$${\ displaystyle a_ {0} = 10 ^ {500} +961+ \ varepsilon}$${\ displaystyle r = 1,01}$${\ displaystyle \ varepsilon}$

Fórmulas principais e funções polinomiais

Sabe-se que não existe nenhuma função polinomial não constante P ( n ) com coeficientes inteiros que avalie um número primo para todos os inteiros n . A prova é a seguinte: suponha que tal polinômio existisse. Então P (1) seria avaliado como um p primo , então . Mas, para qualquer inteiro k , também, não pode ser primo (pois seria divisível por p ) a menos que fosse o próprio p . Mas a única maneira para todo k é se a função polinomial for constante. O mesmo raciocínio mostra um resultado ainda mais forte: não existe nenhuma função polinomial não constante P ( n ) que avalie como um número primo para quase todos os inteiros n . ${\ displaystyle P (1) \ equiv 0 {\ pmod {p}}}$${\ displaystyle P (1 + kp) \ equiv 0 {\ pmod {p}}}$${\ displaystyle P (1 + kp)}$${\ displaystyle P (1 + kp) = P (1) = p}$

Euler notou pela primeira vez (em 1772) que o polinômio quadrático

${\ displaystyle P (n) = n ^ {2} + n + 41}$

é primo para os 40 inteiros n = 0, 1, 2, ..., 39, com os primos correspondentes 41, 43, 47, 53, 61, 71, ..., 1601. As diferenças entre os termos são 2, 4 , 6, 8, 10 ... Para n = 40, ele produz um número quadrado , 1681, que é igual a 41 × 41, o menor número composto para esta fórmula para n ≥ 0. Se 41 divide n , ele divide P ( n ) também. Além disso, como P ( n ) pode ser escrito como n ( n + 1) + 41, se 41 dividir n + 1, ele também divide P ( n ). O fenômeno está relacionado à espiral Ulam , que também é implicitamente quadrática, e ao número da classe ; este polinômio está relacionado ao número de Heegner . Existem polinômios análogos para (os números da sorte de Euler ), correspondendo a outros números de Heegner. ${\ displaystyle 163 = 4 \ cdot 41-1}$${\ displaystyle p = 2,3,5,11 {\ text {e}} 17}$

Dado um número inteiro positivo S , não pode ser infinitamente muitas c de tal forma que a express n ² + n + c é sempre coprime para S . O inteiro c pode ser negativo, caso em que há um atraso antes que os primos sejam produzidos.

Sabe-se, com base no teorema de Dirichlet sobre progressões aritméticas , que funções polinomiais lineares produzir infinitos números primos, enquanto um e b são primos entre si (embora nenhuma tal função irá assumir valores principais para todos os valores de n ). Além disso, o verde-Tao teorema diz que para qualquer k existe um par de um e b , com a propriedade de que é primordial para qualquer n de 0 a K  - 1. No entanto, a partir de 2020, o melhor resultado de tal tipo conhecido é para k = 27: ${\ displaystyle L (n) = an + b}$${\ displaystyle L (n) = an + b}$

${\ displaystyle 224584605939537911 + 18135696597948930n}$

é primo para todo n de 0 a 26. Nem mesmo se sabe se existe um polinômio univariado de grau pelo menos 2, que assume um número infinito de valores que são primos; veja a conjectura de Bunyakovsky .

Fórmula possível usando uma relação de recorrência

Outro gerador principal é definido pela relação de recorrência

${\ displaystyle a_ {n} = a_ {n-1} + \ gcd (n, a_ {n-1}), \ quad a_ {1} = 7,}$

onde mdc ( x , y ) denota o maior divisor comum de x e y . A sequência de diferenças a _{n +1} - a _n começa com 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 47, 3, 1, 5, 3, ... (sequência A132199 no OEIS ). Rowland (2008) provou que essa sequência contém apenas uns e números primos. No entanto, ele não contém todos os números primos, uma vez que os termos mdc ( n + 1, a _n ) são sempre ímpares e, portanto, nunca iguais a 2. 587 é o menor primo (diferente de 2) não aparecendo nos primeiros 10.000 resultados que são diferentes de 1. No entanto, no mesmo artigo foi conjecturado que continha todos os primos ímpares, embora seja bastante ineficiente.

Observe que existe um programa trivial que enumera todos e apenas os números primos, bem como os mais eficientes , de modo que tais relações de recorrência são mais uma questão de curiosidade do que de uso prático.

Veja também

• Teorema do número primo

Referências

Leitura adicional

• Regimbal, Stephen (1975), "Uma fórmula explícita para o k-ésimo número primo", Mathematics Magazine , Mathematical Association of America, 48 (4): 230-232, doi : 10.2307 / 2690354 , JSTOR  2690354.
• Um Venugopalan. Fórmula para primos, primos gêmeos, número de primos e número de primos gêmeos . Proceedings of the Indian Academy of Sciences - Mathematical Sciences, Vol. 92, No 1, setembro de 1983, pp. 49-52 errata

links externos

• Eric W. Weisstein , Prime Formulas ( Prime-Generating Polynomial ) em MathWorld .