Saltar ao contido

Función de contaxe de números primos

Na Galipedia, a Wikipedia en galego.

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 π).

Os valores de π(n) para os primeiros 60 enteiros positivos

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]

Fórmula explícita de Riemann usando os primeiros 200 ceros non triviais da función zeta

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 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)
 % erro
10 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%
Gráfica que mostra a relación da función de contaxe de primos π(x) a dúas das súas aproximacións, x/log x e Li(x). A medida que aumenta x (observe que o eixo x é logarítmico), ambas as razóns tenden cara a 1. A razón para x/log x converxe desde arriba moi lentamente, mentres que a razón para Li(x) converxe máis rápido desde abaixo.

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 in. Entón

Dado un número natural m, se n = π(3m) 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

  1. Bach, Eric; Shallit, Jeffrey (1996). Algorithmic Number Theory. MIT Press. volume 1 page 234 section 8.8. ISBN 0-262-02405-5. 
  2. Weisstein, Eric W. "Prime Counting Function". MathWorld. 
  3. 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. 
  4. Dickson, Leonard Eugene (2005). History of the Theory of Numbers, Vol. I: Divisibility and Primality. Dover Publications. ISBN 0-486-44232-2. 
  5. Ireland, Kenneth; Rosen, Michael (1998). A Classical Introduction to Modern Number Theory (Second ed.). Springer. ISBN 0-387-97329-X. 
  6. Ver Teorema 23 de A. E. Ingham (2000). The Distribution of Prime Numbers. Cambridge University Press. ISBN 0-521-39789-8. 
  7. 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. 
  8. Hutama, Daniel (2017). "Implementation of Riemann's Explicit Formula for Rational and Gaussian Primes in Sage" (PDF). Institut des sciences mathématiques. 
  9. 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. 
  10. "Táboas de valores de π(x) e de π2(x)". Tomás Oliveira e Silva. Consultado o 2024-03-31. 
  11. "Unha táboa de valores de π(x)". Xavier Gourdon, Pascal Sebah, Patrick Demichel. Consultado o 2008-09-14. 
  12. "Conditional Calculation of π(1024)". Chris K. Caldwell. Consultado o 2024-03-30. 
  13. Platt, David J. (2012). "Computing π(x) Analytically)". arXiv:1203.5712 [math.NT]. 
  14. Walisch, Kim (September 6, 2015). "New confirmed π(1027) prime counting function record". Mersenne Forum. 
  15. Baugh, David (August 30, 2020). "New prime counting function record, pi(10^28)". Mersenne Forum. 
  16. Walisch, Kim (March 4, 2022). "New prime counting function record: PrimePi(10^29)". Mersenne Forum. 
  17. Apostol, Tom M. (2010). Introduction to Analytic Number Theory. Springer. 
  18. Titchmarsh, E.C. (1960). The Theory of Functions, 2nd ed. Oxford University Press. 
  19. Weisstein, Eric W. "Riemann Prime Counting Function". MathWorld. 
  20. 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. 
  21. Weisstein, Eric W. "Gram Series". MathWorld. 
  22. "The encoding of the prime distribution by the zeta zeros". Matthew Watkins. Consultado o 2008-09-14. 
  23. 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]

Bibliografía

[editar | editar a fonte]

Outros artigos

[editar | editar a fonte]

Ligazóns externas

[editar | editar a fonte]