Función de contaxe de números primos
En matemáticas, a función de contaxe de números primos é a función que conta o número de números primos menores ou igual a algún número real x.[1][2] Desígnase por π(x) (sen relación co número π).
Taxa de crecemento
[editar | editar a fonte]De gran interese na teoría de números é a taxa de crecemento da función de contaxe de primos.[3][4] Foi conxecturado a finais do século XVIII por Gauss e por Legendre como aproximadamente
onde log é o logaritmo natural, no sentido de que
Esta afirmación é o teorema dos números primos. Unha afirmación equivalente é
- ,
onde é a función logaritmo integral.
O teorema dos números primos foi probado por primeira vez en 1896 por Jacques Hadamard e por Charles de la Vallée Poussin de forma independente, utilizando as propiedades da función zeta de Riemann introducida por Riemann en 1859. Atle Selberg e Paul Erdős atoparon probas do teorema dos números primos que non empregaban a función zeta nin a análise complexa arredor de 1948 (na súa maior parte de forma independente).[5]
Estimacións máis precisas
[editar | editar a fonte]No 1899, de la Vallée Poussin probou que [6]
Agora coñécense estimacións máis precisas de π(x). Por exemplo, en 2002, Kevin Ford demostrou que[7]
Para valores de x que non sexan excesivamente grandes, li(x) é maior que π(x). Porén, π(x) − li(x) sábese que muda de signo infinitas veces. Para unha discusión sobre isto, consulte o número de Skewes.
Forma exacta
[editar | editar a fonte]Para x > 1 sexa π0(x) = π(x) − 1/2 cando x é un número primo, e π0(x) = π(x) doutro xeito. Bernhard Riemann, na súa obra Sobre o número de primos menores que unha magnitude dada, demostrou que π0(x) é igual a[8]
onde
e aquí μ(n) é a función de Möbius, li(x) é o logaritmo integral, ρ indexa cada cero da función zeta de Riemann. Se se recollen os ceros triviais e a suma tómase só sobre os ceros non triviais ρ da función zeta de Riemann, entón π0(x) pode ser aproximado por[9]
A hipótese de Riemann suxire que cada cero non trivial deste tipo está ao longo de Re(s) = 1/2.
Táboa de π(x) , x/log(x), e li(x)
[editar | editar a fonte]A táboa mostra as tres funcións π(x), x/log(x) e li(x) comparadas nas potencias de 10. Ver tamén,[3][10] e[11]
x π(x) π(x) − x/log(x) li(x) − π(x) x/π(x) x/log(x)
% erro10 4 0 2 2.500 −8.57% 102 25 3 5 4.000 +13.14% 103 168 23 10 5.952 +13.83% 104 1,229 143 17 8.137 +11.66% 105 9,592 906 38 10.425 +9.45% 106 78,498 6,116 130 12.739 +7.79% 107 664,579 44,158 339 15.047 +6.64% 108 5,761,455 332,774 754 17.357 +5.78% 109 50,847,534 2,592,592 1,701 19.667 +5.10% 1010 455,052,511 20,758,029 3,104 21.975 +4.56% 1011 4,118,054,813 169,923,159 11,588 24.283 +4.13% 1012 37,607,912,018 1,416,705,193 38,263 26.590 +3.77% 1013 346,065,536,839 11,992,858,452 108,971 28.896 +3.47% 1014 3,204,941,750,802 102,838,308,636 314,890 31.202 +3.21% 1015 29,844,570,422,669 891,604,962,452 1,052,619 33.507 +2.99% 1016 279,238,341,033,925 7,804,289,844,393 3,214,632 35.812 +2.79% 1017 2,623,557,157,654,233 68,883,734,693,928 7,956,589 38.116 +2.63% 1018 24,739,954,287,740,860 612,483,070,893,536 21,949,555 40.420 +2.48% 1019 234,057,667,276,344,607 5,481,624,169,369,961 99,877,775 42.725 +2.34% 1020 2,220,819,602,560,918,840 49,347,193,044,659,702 222,744,644 45.028 +2.22% 1021 21,127,269,486,018,731,928 446,579,871,578,168,707 597,394,254 47.332 +2.11% 1022 201,467,286,689,315,906,290 4,060,704,006,019,620,994 1,932,355,208 49.636 +2.02% 1023 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309 7,250,186,216 51.939 +1.93% 1024 18,435,599,767,349,200,867,866 339,996,354,713,708,049,069 17,146,907,278 54.243 +1.84% 1025 176,846,309,399,143,769,411,680 3,128,516,637,843,038,351,228 55,160,980,939 56.546 +1.77% 1026 1,699,246,750,872,437,141,327,603 28,883,358,936,853,188,823,261 155,891,678,121 58.850 +1.70% 1027 16,352,460,426,841,680,446,427,399 267,479,615,610,131,274,163,365 508,666,658,006 61.153 +1.64% 1028 157,589,269,275,973,410,412,739,598 2,484,097,167,669,186,251,622,127 1,427,745,660,374 63.456 +1.58% 1029 1,520,698,109,714,272,166,094,258,063 23,130,930,737,541,725,917,951,446 4,551,193,622,464 65.759 +1.52%
Na On-Line Encyclopedia of Integer Sequences, a columna π(x) é a (secuencia A006880 na OEIS), π(x) − x/log x é a (secuencia A057835 na OEIS) e li(x) − π(x) é a (secuencia A057752 na OEIS).
O valor de π(1024) foi calculado orixinalmente por J. Buethe, J. Franke, A. Jost e T. Kleinjung asumindo a hipótese de Riemann.[12] Máis tarde comprobouse sen condicións nun cálculo de DJ Platt. O valor de π(1025) débese a J. Buethe, J. Franke, A. Jost e T. Kleinjung.[13] O valor de π(1026) foi calculado por DB Staple. Todas as demais entradas anteriores nesta táboa tamén foron verificadas como parte dese traballo.
Os valores para 1027, 1028 e 1029 foron anunciados por David Baugh e Kim Walisch en 2015,[14] 2020,[15] e 2022,[16] respectivamente.
Algoritmos para avaliar π(x)
[editar | editar a fonte]Unha forma sinxela de atopar π(x), se x non é demasiado grande, é usar a creba de Eratóstenes para producir os primos menores ou iguais a x e despois contalos.
Unha forma máis elaborada de atopar π(x) débese a Legendre (usando o principio de inclusión-exclusión): dado x, se p1, p2,…, pn son números primos distintos, entón o número de enteiros menor que ou iguais a x que non son divisíbeis por ningún pi é
(onde ⌊x⌋ denota a función chan). Este número é, polo tanto, igual a
cando os números p1, p2,…, pn son os números primos menores ou iguais á raíz cadrada de x.
Algoritmo de Meissel-Lehmer
[editar | editar a fonte]- Artigo principal: Algoritmo de Meissel–Lehmer.
Nunha serie de artigos publicados entre 1870 e 1885, Ernst Meissel describiu (e utilizou) unha forma combinatoria práctica de avaliar π(x): Sexan p1, p2,…, pn os primeiros n primos e denotémos por Φ(m,n) o número de números naturais non superiores a m que non son divisíbeis por ningún dos pi para calquera i ≤ n. Entón
Dado un número natural m, se n = π(3√m) e se μ = π(√m) − n, entón
Usando este enfoque, Meissel calculou π(x), para x igual a 5×105, 106, 107, e 108.
En 1959, Derrick Henry Lehmer ampliou e simplificou o método de Meissel
Outras funcións de contaxe de primos
[editar | editar a fonte]Función de Riemann de contaxe de potencias de primos
[editar | editar a fonte]Adoita denotarse como Π0(x) ou J0(x). Ten saltos de
Formalmente, podemos definir Π0(x) por
onde a variable p en cada suma varía sobre todos os primos dentro dos límites especificados.
Tamén podemos escribir
onde Λ é a función de von Mangoldt e
A fórmula de inversión de Möbius dá logo
onde μ(n) é a función de Möbius.
Coñecendo a relación entre o logaritmo da función zeta de Riemann e a función de von Mangoldt Λ, e utilizando a fórmula de Perron temos
- .
Función de Chebyshev
[editar | editar a fonte]A función de Chebyshev pondera números primos ou potencias de primos pn mediante log(p) :
Para x ≥ 2,[17]
e
Fórmulas para as funcións de contaxe de números primos
[editar | editar a fonte]As fórmulas para as funcións de contaxe de primos son de dous tipos: fórmulas aritméticas e fórmulas analíticas. As fórmulas analíticas para a contaxe de primos foron as primeiras utilizadas para demostrar o teorema dos números primos. Procedentes do traballo de Riemann e von Mangoldt, coñécense xeralmente como fórmulas explícitas.[18]
Temos a seguinte expresión para a segunda función de Chebyshev ψ:
onde
Aquí ρ son os ceros da función zeta de Riemann na franxa crítica, onde a parte real de ρ está entre cero e un. A fórmula é válida para valores de x maiores que un, que é a rexión de interese. A suma sobre as raíces é condicionalmente converxente e debe tomarse por orde crecente do valor absoluto da parte imaxinaria. Teña en conta que a mesma suma sobre as raíces triviais dá o último sustraendo da fórmula.
Para Π0(x) temos unha fórmula máis complicada
De novo, a fórmula é válida para x > 1, mentres que ρ son os ceros non triviais da función zeta ordenados segundo o seu valor absoluto. A integral é igual á serie sobre os ceros triviais:
O primeiro termo li(x) é o logaritmo integral usual; a expresión li(xρ) no segundo termo debería considerarse como Ei(ρ log x), onde Ei é a continuación analítica da función integral exponencial desde os reais negativos ata o plano complexo coa ramificación cortada ao longo dos reais positivos.
Así, a fórmula de inversión de Möbius dános [9]
válido para x > 1, onde
é a función R de Riemann[19] e μ(n) é a función de Möbius. Esta última serie coñécese como serie de Gram.[20][21] Como log x < x para todo x > 0, esta serie converxe para todo x positivo en comparación coa serie para ex.
A suma sobre os ceros non triviais de zeta na fórmula para π0(x) describe as flutuacións de π0(x) mentres que os termos restantes dan a parte "suave" da función de contaxe de primos,[22], asi que pódese usar
como un bo estimador de π(x) para x > 1.
De feito, xa que o segundo termo achégase a 0 cando x → ∞, mentres que a amplitude da parte "ruidosa" é heurísticamente aproximado a √x/log x, estimando π(x) só por R(x) é igual de bo, e as flutuacións da distribución dos números primos poden representarse claramente coa función
A hipótese de Riemann
[editar | editar a fonte]A hipótese de Riemann implica un límite moito máis estreito do erro na estimación de π(x) e, polo tanto, unha distribución máis regular dos números primos,
En concreto,[23]
Dudek (2015) probou que a hipótese de Riemann implica que para todo x ≥ 2 hai un primo p a satisfacer
Notas
[editar | editar a fonte]- ↑ Bach, Eric; Shallit, Jeffrey (1996). Algorithmic Number Theory. MIT Press. volume 1 page 234 section 8.8. ISBN 0-262-02405-5.
- ↑ Weisstein, Eric W. "Prime Counting Function". MathWorld.
- ↑ 3,0 3,1 "How many primes are there?". Chris K. Caldwell. Arquivado dende o orixinal o 2012-10-15. Consultado o 2008-12-02.
- ↑ Dickson, Leonard Eugene (2005). History of the Theory of Numbers, Vol. I: Divisibility and Primality. Dover Publications. ISBN 0-486-44232-2.
- ↑ Ireland, Kenneth; Rosen, Michael (1998). A Classical Introduction to Modern Number Theory (Second ed.). Springer. ISBN 0-387-97329-X.
- ↑ Ver Teorema 23 de A. E. Ingham (2000). The Distribution of Prime Numbers. Cambridge University Press. ISBN 0-521-39789-8.
- ↑ Kevin Ford (November 2002). "Vinogradov's Integral and Bounds for the Riemann Zeta Function" (PDF). Proc. London Math. Soc. 85 (3): 565–633. arXiv:1910.08209. doi:10.1112/S0024611502013655.
- ↑ Hutama, Daniel (2017). "Implementation of Riemann's Explicit Formula for Rational and Gaussian Primes in Sage" (PDF). Institut des sciences mathématiques.
- ↑ 9,0 9,1 Riesel, Hans; Göhl, Gunnar (1970). "Some calculations related to Riemann's prime number formula" (PDF). Mathematics of Computation (American Mathematical Society) 24 (112): 969–983. ISSN 0025-5718. JSTOR 2004630. MR 0277489. doi:10.2307/2004630.
- ↑ "Táboas de valores de π(x) e de π2(x)". Tomás Oliveira e Silva. Consultado o 2024-03-31.
- ↑ "Unha táboa de valores de π(x)". Xavier Gourdon, Pascal Sebah, Patrick Demichel. Consultado o 2008-09-14.
- ↑ "Conditional Calculation of π(1024)". Chris K. Caldwell. Consultado o 2024-03-30.
- ↑ Platt, David J. (2012). "Computing π(x) Analytically)". arXiv:1203.5712 [math.NT].
- ↑ Walisch, Kim (September 6, 2015). "New confirmed π(1027) prime counting function record". Mersenne Forum.
- ↑ Baugh, David (August 30, 2020). "New prime counting function record, pi(10^28)". Mersenne Forum.
- ↑ Walisch, Kim (March 4, 2022). "New prime counting function record: PrimePi(10^29)". Mersenne Forum.
- ↑ Apostol, Tom M. (2010). Introduction to Analytic Number Theory. Springer.
- ↑ Titchmarsh, E.C. (1960). The Theory of Functions, 2nd ed. Oxford University Press.
- ↑ Weisstein, Eric W. "Riemann Prime Counting Function". MathWorld.
- ↑ Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics 126 (2nd ed.). Birkhäuser. pp. 50–51. ISBN 0-8176-3743-5.
- ↑ Weisstein, Eric W. "Gram Series". MathWorld.
- ↑ "The encoding of the prime distribution by the zeta zeros". Matthew Watkins. Consultado o 2008-09-14.
- ↑ Schoenfeld, Lowell (1976). "Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II". Mathematics of Computation (American Mathematical Society) 30 (134): 337–360. ISSN 0025-5718. JSTOR 2005976. MR 0457374. doi:10.2307/2005976.
Véxase tamén
[editar | editar a fonte]Wikimedia Commons ten máis contidos multimedia na categoría: Función de contaxe de números primos |
Bibliografía
[editar | editar a fonte]- Dudek, Adrian W. (2015). On the Riemann hypothesis and the difference between primes. International Journal of Number Theory 11. pp. 771–778. Bibcode:2014arXiv1402.6417D. ISSN 1793-0421. arXiv:1402.6417. doi:10.1142/S1793042115500426.
Outros artigos
[editar | editar a fonte]Ligazóns externas
[editar | editar a fonte]- Chris Caldwell, The Nth Prime Page at The Prime Pages.
- Tomás Oliveira e Silva, Tables of prime-counting functions.