En las matemáticas , la función principal de conteo es la función de contar el número de números primos menores o iguales a algún número real x . [1] [2] Se denota por π ( x ) (no relacionado con el número π ).
Historia
De gran interés en la teoría de números es la tasa de crecimiento de la función de conteo de primos. [3] [4] Fue conjeturado a finales del siglo XVIII por Gauss y por Legendre que era aproximadamente
en el sentido de que
Esta declaración es el teorema de los números primos . Una declaración equivalente es
donde li es la función integral logarítmica . El teorema del número primo se demostró por primera vez en 1896 por Jacques Hadamard y por Charles de la Vallée Poussin independientemente, utilizando las propiedades de la función zeta de Riemann introducido por Riemann en 1859. Las pruebas de la número primo teorema no utilizando la función zeta o análisis complejo fueron encontrados alrededor de 1948 por Atle Selberg y por Paul Erdős (en su mayor parte de forma independiente). [5]
En 1899, de la Vallée Poussin demostró que (ver también Teorema 23 de [6] )
para alguna constante positiva a . Aquí, O (...) es la notación O grande .
Estimaciones más precisas de ahora se conocen. Por ejemplo, en 2002, Kevin Ford demostró que [7]
- .
En 2016, Tim Trudgian demostró un límite superior explícito para la diferencia entre y :
por . [8]
Para la mayoría de los valores de estamos interesados en (es decir, cuando no es excesivamente grande) es mayor que . Sin emabargo,se sabe que cambia de signo infinitas veces. Para una discusión de esto, vea el número de Skewes .
Forma exacta
De profunda importancia, Bernhard Riemann demostró que la función de conteo de primos es exactamente [9]
dónde
- ,
μ ( n ) es la función de Möbius , li ( x ) es la función integral logarítmica , ρ indexa cada cero de la función zeta de Riemann y li ( x ρ / n ) no se evalúa con un corte de rama sino que se considera como Ei (ρ/norteln x ) donde Ei ( x ) es la integral exponencial . De manera equivalente, si se recopilan los ceros triviales y la suma se toma solo sobre los ceros no triviales ρ de la función zeta de Riemann , entonces π ( x ) puede escribirse
- .
La hipótesis de Riemann sugiere que cada cero no trivial se encuentra a lo largo de Re ( s ) = 1/2.
Tabla de π ( x ), x / ln x y li ( x )
La tabla muestra cómo las tres funciones π ( x ), x / ln x y li ( x ) se comparan a potencias de 10. Ver también, [3] [10] [11] y [12]
X π ( x ) π ( x ) - x / ln x li ( x ) - π ( x ) x / π ( x ) x / ln x % de error 10 4 −0,3 2.2 2.500 -7,5% 10 2 25 3.3 5.1 4.000 13,20% 10 3 168 23 10 5.952 13,69% 10 4 1,229 143 17 8.137 11,64% 10 5 9.592 906 38 10.425 9,45% 10 6 78,498 6.116 130 12.740 7,79% 10 7 664,579 44,158 339 15.047 6,64% 10 8 5.761.455 332,774 754 17.357 5,78% 10 9 50,847,534 2,592,592 1,701 19.667 5,10% 10 10 455,052,511 20,758,029 3.104 21,975 4,56% 10 11 4.118.054.813 169,923,159 11.588 24.283 4,13% 10 12 37,607,912,018 1.416.705.193 38.263 26.590 3,77% 10 13 346,065,536,839 11.992.858.452 108,971 28.896 3,47% 10 14 3.204.941.750.802 102,838,308,636 314,890 31.202 3,21% 10 15 29,844,570,422,669 891.604.962.452 1.052.619 33.507 2,99% 10 16 279,238,341,033,925 7.804.289.844.393 3,214,632 35.812 2,79% 10 17 2,623,557,157,654,233 68,883,734,693,281 7,956,589 38.116 2,63% 10 18 24,739,954,287,740,860 612,483,070,893,536 21,949,555 40.420 2,48% 10 19 234,057,667,276,344,607 5.481.624.169.369.960 99,877,775 42.725 2,34% 10 20 2,220,819,602,560,918,840 49,347,193,044,659,701 222,744,644 45.028 2,22% 10 21 21,127,269,486,018,731,928 446,579,871,578,168,707 597,394,254 47.332 2,11% 10 22 201,467,286,689,315,906,290 4.060.704.006.019.620.994 1,932,355,208 49.636 2,02% 10 23 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309 7.250.186.216 51,939 1,93% 10 24 18,435,599,767,349,200,867,866 339.996.354.713.708.049.069 17.146.907.278 54.243 1,84% 10 25 176,846,309,399,143,769,411,680 3.128.516.637.843.038.351.228 55,160,980,939 56.546 1,77% 10 26 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% 10 27 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%
En la Enciclopedia en línea de secuencias de enteros , la columna π ( x ) es la secuencia OEIS : A006880 , π ( x ) - x / ln x es la secuencia OEIS : A057835 y li ( x ) - π ( x ) es la secuencia OEIS : A057752 .
El valor de π (10 24 ) fue calculado originalmente por J. Buethe, J. Franke , A. Jost y T. Kleinjung asumiendo la hipótesis de Riemann . [13] Posteriormente se verificó incondicionalmente en un cálculo de DJ Platt. [14] El valor de π (10 25 ) se debe a J. Buethe, J. Franke , A. Jost y T. Kleinjung. [15] El valor de π (10 26 ) fue calculado por DB Staple. [16] Todas las demás entradas anteriores de esta tabla también se verificaron como parte de ese trabajo.
El valor de 10 27 fue publicado en 2015 por David Baugh y Kim Walisch. [17]
Algoritmos para evaluar π ( x )
Una forma sencilla de encontrar , Si no es demasiado grande, es utilizar el tamiz de Eratóstenes para producir los primos menores o iguales a y luego contarlos.
Una forma más elaborada de encontrar se debe a Legendre (utilizando el principio de inclusión-exclusión ): dado, Si son números primos distintos, entonces el número de enteros menores o iguales a que son divisibles por no es
(dónde denota la función de piso ). Por tanto, este número es igual a
cuando los numeros son los números primos menores o iguales que la raíz cuadrada de .
El algoritmo de Meissel-Lehmer
En una serie de artículos publicados entre 1870 y 1885, Ernst Meissel describió (y utilizó) una forma práctica combinatoria de evaluar. Dejar sé el primero primos y denotar por el número de números naturales no mayor que que son divisibles por no . Luego
Dado un número natural , Si y si , luego
Usando este enfoque, Meissel calculó , por igual a 5 × 10 5 , 10 6 , 10 7 y 10 8 .
En 1959, Derrick Henry Lehmer amplió y simplificó el método de Meissel. Definir, de verdad y para números naturales y , como el número de números no mayor que m con exactamente k factores primos, todos mayores que. Además, establezca. Luego
donde la suma en realidad tiene sólo un número finito de términos distintos de cero. Dejar denotar un número entero tal que , y establecer . Luego y Cuándo . Por lo tanto,
El cálculo de se puede obtener de esta manera:
donde la suma está sobre números primos.
Por otro lado, el cálculo de se puede hacer usando las siguientes reglas:
Usando su método y un IBM 701 , Lehmer pudo calcular.
Lagarias, Miller, Odlyzko, Deléglise y Rivat realizaron más mejoras en este método. [18]
Otras funciones de conteo de primos
También se utilizan otras funciones de conteo primo porque es más conveniente trabajar con ellas. Uno es la función de conteo de primos de Riemann, generalmente denotada como o . Esto tiene saltos de 1 / n para los poderes primos p n , y toma un valor a la mitad entre los dos lados en las discontinuidades. Ese detalle adicional se usa porque entonces la función puede definirse mediante una transformada de Mellin inversa . Formalmente, podemos definir por
donde p es primo.
También podemos escribir
dónde es la función de von Mangoldt y
La fórmula de inversión de Möbius da
Conocer la relación entre el logaritmo de la función zeta de Riemann y la función de von Mangoldt , y usando la fórmula de Perron tenemos
La función de Chebyshev pondera los números primos o potencias primos p n por ln ( p ):
Fórmulas para funciones de conteo de primos
Las fórmulas para las funciones de conteo de primos vienen en dos tipos: fórmulas aritméticas y fórmulas analíticas. Las fórmulas analíticas para el conteo de primos fueron las primeras que se utilizaron para demostrar el teorema de los números primos . Provienen del trabajo de Riemann y von Mangoldt , y generalmente se conocen como fórmulas explícitas . [19]
Tenemos la siguiente expresión para ψ :
dónde
Aquí ρ son los ceros de la función zeta de Riemann en la franja crítica, donde la parte real de ρ está entre cero y uno. La fórmula es válida para valores de x mayores que uno, que es la región de interés. La suma de las raíces es condicionalmente convergente y debe tomarse en orden de aumento del valor absoluto de la parte imaginaria. Tenga en cuenta que la misma suma sobre las raíces triviales da el último sustraendo en la fórmula.
Para tenemos una formula mas complicada
Nuevamente, la fórmula es válida para x > 1, mientras que ρ son los ceros no triviales de la función zeta ordenados de acuerdo con su valor absoluto y, nuevamente, la última integral, tomada con el signo menos, es la misma suma, pero sobre el ceros triviales. El primer término li ( x ) es la función integral logarítmica habitual ; la expresión li ( x ρ ) en el segundo término debe considerarse como Ei ( ρ ln x ), donde Ei es la continuación analítica de la función integral exponencial de reales negativos al plano complejo con rama cortada a lo largo de reales positivos.
Por lo tanto, la fórmula de inversión de Möbius nos da [20]
válido para x > 1, donde
es la función R de Riemann [21] y μ ( n ) es la función de Möbius . La última serie se conoce como serie Gram . [22] [23] Porque para todos , esta serie converge para todo x positivo en comparación con la serie para.
La suma sobre ceros zeta no triviales en la fórmula para describe las fluctuaciones de mientras que los términos restantes dan la parte "suave" de la función de conteo de primos, [24] por lo que se puede usar
como el mejor estimador de para x > 1.
La amplitud de la parte "ruidosa" se trata heurísticamente de por lo que las fluctuaciones de la distribución de primos se pueden representar claramente con la función Δ:
Está disponible una tabla extensa de los valores de Δ ( x ). [11]
Desigualdades
Aquí hay algunas desigualdades útiles para π ( x ).
para x ≥ 17.
La desigualdad de la izquierda es válida para x ≥ 17 y la desigualdad de la derecha es válida para x > 1. La constante 1.25506 es a 5 lugares decimales, como tiene su valor máximo en x = 113. [25]
Pierre Dusart demostró en 2010:
- por , y
- por . [26]
Aquí hay algunas desigualdades para el n- ésimo primo, p n . El límite superior se debe a Rosser (1941), [27] el inferior a Dusart (1999): [28]
para n ≥ 6.
La desigualdad de la izquierda es válida para n ≥ 2 y la desigualdad de la derecha es válida para n ≥ 6.
Una aproximación para el n- ésimo número primo es
Ramanujan [29] demostró que la desigualdad
se cumple para todos los valores suficientemente grandes de .
En [26] Dusart demostró (Proposición 6.6) que, para,
y (Proposición 6.7) que, para ,
Más recientemente, Dusart [30] ha demostrado (Teorema 5.1) que, para,
- ,
y eso, por ,
La hipótesis de Riemann
La hipótesis de Riemann es equivalente a un límite mucho más estricto del error en la estimación para, y por lo tanto a una distribución más regular de números primos,
En concreto, [31]
Ver también
- Constante de foias
- Postulado de Bertrand
- La conjetura de oppermann
- Ramanujan prime
Referencias
- ^ Bach, Eric; Shallit, Jeffrey (1996). Teoría algorítmica de números . Prensa del MIT. volumen 1 página 234 sección 8.8. ISBN 0-262-02405-5.
- ^ Weisstein, Eric W. "Función de conteo principal" . MathWorld .
- ^ a b "¿Cuántos números primos hay?" . Chris K. Caldwell . Consultado el 2 de diciembre de 2008 .
- ^ Dickson, Leonard Eugene (2005). Historia de la teoría de los números, vol. I: Divisibilidad y Primalidad . Publicaciones de Dover. ISBN 0-486-44232-2.
- ^ Irlanda, Kenneth; Rosen, Michael (1998). Una introducción clásica a la teoría de números moderna (segunda ed.). Saltador. ISBN 0-387-97329-X.
- ^ AE Ingham (2000). La distribución de números primos . Prensa de la Universidad de Cambridge. ISBN 0-521-39789-8.
- ^ Kevin Ford (noviembre de 2002). "Integral y límites de Vinogradov para la función Riemann Zeta" (PDF) . Proc. London Math. Soc . 85 (3): 565–633. arXiv : 1910.08209 . doi : 10.1112 / S0024611502013655 . S2CID 121144007 .
- ^ Tim Trudgian (febrero de 2016). "Actualización del término de error en el teorema de los números primos". Diario Ramanujan . 39 (2): 225–234. arXiv : 1401.2689 . doi : 10.1007 / s11139-014-9656-6 . S2CID 11013503 .
- ^ "Las fluctuaciones de la función de conteo de primos pi (x)" . www.primefan.ru . Consultado el 17 de mayo de 2019 .
- ^ "Tablas de valores de pi (x) y de pi2 (x)" . Tomás Oliveira e Silva . Consultado el 14 de septiembre de 2008 .
- ^ a b "Valores de π ( x ) y Δ ( x ) para varios valores de x " . Andrey V. Kulsha . Consultado el 14 de septiembre de 2008 .
- ^ "Una tabla de valores de pi (x)" . Xavier Gourdon, Pascal Sebah, Patrick Demichel . Consultado el 14 de septiembre de 2008 .
- ^ "Cálculo condicional de pi (10 24 )" . Chris K. Caldwell . Consultado el 3 de agosto de 2010 .
- ^ Platt, David J. (2012). "Computación π ( x ) analíticamente)". arXiv : 1203.5712 [ matemáticas.NT ].
- ^ "¿Cuántos Primes hay?" . J. Buethe . Consultado el 1 de septiembre de 2015 .
- ^ Staple, Douglas (19 de agosto de 2015). El algoritmo combinatorio para calcular pi (x) (Tesis). Universidad de Dalhousie . Consultado el 1 de septiembre de 2015 .
- ^ Walisch, Kim (6 de septiembre de 2015). "Nuevo registro de función de conteo principal pi (10 ^ 27) confirmado" . Foro de Mersenne .
- ^ Marc Deleglise; Joel Rivat (enero de 1996). "Computación π ( x ): El método de Meissel, Lehmer, Lagarias, Miller, Odlyzko" (PDF) . Matemáticas de la Computación . 65 (213): 235–245. doi : 10.1090 / S0025-5718-96-00674-6 .
- ^ Titchmarsh, CE (1960). La teoría de las funciones, 2ª ed . Prensa de la Universidad de Oxford.
- ^ Riesel, Hans ; Göhl, Gunnar (1970). "Algunos cálculos relacionados con la fórmula de números primos de Riemann". Matemáticas de la Computación . Sociedad Matemática Estadounidense. 24 (112): 969–983. doi : 10.2307 / 2004630 . ISSN 0025-5718 . JSTOR 2004630 . Señor 0277489 .
- ^ Weisstein, Eric W. "Riemann Prime Counting Function" . MathWorld .
- ^ Riesel, Hans (1994). Números primos y métodos informáticos de factorización . Progreso en Matemáticas. 126 (2ª ed.). Birkhäuser. págs. 50–51. ISBN 0-8176-3743-5.
- ^ Weisstein, Eric W. "Serie Gram" . MathWorld .
- ^ "La codificación de la distribución prima por los zeta ceros" . Matthew Watkins . Consultado el 14 de septiembre de 2008 .
- ^ Rosser, J. Barkley ; Schoenfeld, Lowell (1962). "Fórmulas aproximadas para algunas funciones de números primos" . Illinois J. Math . 6 : 64–94. doi : 10.1215 / ijm / 1255631807 . ISSN 0019-2082 . Zbl 0122.05001 .
- ^ a b Dusart, Pierre (2 de febrero de 2010). "Estimaciones de algunas funciones sobre primos sin HR". arXiv : 1002.0442v1 [ matemáticas.NT ].
- ^ Rosser, Barkley (1941). "Límites explícitos para algunas funciones de números primos". Revista Estadounidense de Matemáticas . 63 (1): 211–232. doi : 10.2307 / 2371291 . JSTOR 2371291 .
- ^ Dusart, Pierre (1999). "El k-ésimo primo es mayor que k (lnk + lnlnk-1) para k> = 2" . Matemáticas de la Computación . 68 (225): 411–415. doi : 10.1090 / S0025-5718-99-01037-6 .
- ^ Berndt, Bruce C. (6 de diciembre de 2012). Cuadernos de Ramanujan, Parte IV . Springer Science & Business Media. págs. 112-113. ISBN 9781461269328.
- ^ Dusart, Pierre (enero de 2018). "Estimaciones explícitas de algunas funciones sobre primos". Diario Ramanujan . 45 (1): 225–234. doi : 10.1007 / s11139-016-9839-4 . S2CID 125120533 .
- ^ Schoenfeld, Lowell (1976). "Límites más nítidos para las funciones de Chebyshev θ ( x ) y ψ ( x ). II". Matemáticas de la Computación . Sociedad Matemática Estadounidense. 30 (134): 337–360. doi : 10.2307 / 2005976 . ISSN 0025-5718 . JSTOR 2005976 . Señor 0457374 .
enlaces externos
- Chris Caldwell, The Nth Prime Page en The Prime Pages .
- Tomás Oliveira e Silva, Tablas de funciones de conteo de primos .