En teoría de números , una fórmula para números primos es una fórmula que genera los números primos , exactamente y sin excepción. No se conoce ninguna fórmula que sea eficientemente computable . Se conocen una serie de limitaciones que muestran lo que una "fórmula" de este tipo puede y no puede ser.
Fórmula basada en el teorema de Wilson
Una fórmula simple es
para entero positivo , dónde es la función de piso , que se redondea al número entero más cercano. Por el teorema de Wilson , es primo si y solo si . Por lo tanto, cuando es primo, el primer factor del producto se convierte en uno y la fórmula produce el número primo . Pero cuandono es primo, el primer factor se convierte en cero y la fórmula produce el número primo 2. [1] Esta fórmula no es una forma eficiente de generar números primos porque evaluar requiere sobre multiplicaciones y reducciones .
Fórmula basada en un sistema de ecuaciones diofánticas
Debido a que el conjunto de primos es un conjunto computablemente enumerable , según el teorema de Matiyasevich , se puede obtener a partir de un sistema de ecuaciones diofánticas . Jones y col. (1976) encontraron un conjunto explícito de 14 ecuaciones diofánticas en 26 variables, de modo que un número dado k + 2 es primo si y solo si ese sistema tiene una solución en números naturales : [2]
Las 14 ecuaciones α 0 ,…, α 13 se pueden usar para producir una desigualdad polinómica generadora de primos en 26 variables:
es decir:
es una desigualdad polinomial en 26 variables, y el conjunto de números primos es idéntico al conjunto de valores positivos tomados por el lado izquierdo cuando las variables a , b ,…, z se extienden sobre los enteros no negativos.
Un teorema general de Matiyasevich dice que si un conjunto está definido por un sistema de ecuaciones diofánticas, también puede ser definido por un sistema de ecuaciones diofánticas en solo 9 variables. [3] Por lo tanto, hay un polinomio generador de primos como el anterior con solo 10 variables. Sin embargo, su grado es grande (del orden de 10 45 ). Por otro lado, también existe un conjunto de ecuaciones de grado solo 4, pero en 58 variables. [4]
Fórmula de molinos
La primera fórmula conocida fue establecida por WH Mills ( 1947 ), quien demostró que existe un número real A tal que, si
luego
es un número primo para todos los enteros positivos n . [5] Si la hipótesis de Riemann es cierta, entonces el valor más pequeño de A tiene un valor de alrededor de 1,3063778838630806904686144926 ... (secuencia A051021 en la OEIS ) y se conoce como constante de Mills . Este valor da lugar a los primos, , , ... (secuencia A051254 en la OEIS ). Se sabe muy poco sobre la constante A (ni siquiera si es racional ). Esta fórmula no tiene valor práctico, porque no existe una forma conocida de calcular la constante sin encontrar primos en primer lugar.
Tenga en cuenta que no hay nada especial en la función de suelo en la fórmula. Tóth [6] demostró que también existe una constante tal que
también es el principal representante de ( Tóth 2017 ).
En el caso , el valor de la constante comienza con 1.24055470525201424067 ... Los primeros números primos generados son:
Sin asumir la hipótesis de Riemann, Elsholtz desarrolló varias funciones de representación de primos similares a las de Mills. Por ejemplo, si, luego es primo para todos los enteros positivos . Del mismo modo, si, luego es primo para todos los enteros positivos . [7]
Fórmula de Wright
Otra fórmula generadora de primos similar a la de Mills proviene de un teorema de EM Wright . Demostró que existe un número real α tal que, si
- y
- por ,
luego
es primordial para todos . [8] Wright da los primeros siete lugares decimales de dicha constante:. Este valor da lugar a los primos, , y . es par , por lo que no es primo. Sin embargo, con, , , y no cambian, mientras que es primo con 4932 dígitos. [9] Esta secuencia de números primos no puede extenderse más allá de sin saber más dígitos de . Como la fórmula de Mills, y por las mismas razones, la fórmula de Wright no se puede usar para encontrar números primos.
Una función que representa todos los números primos.
Dada la constante por , define la secuencia
( 1 )
dónde es la función de piso . Entonces para, es igual al th primo: , , , etc. [10] La constante inicialdada en el artículo es lo suficientemente precisa para que la ecuación ( 1 ) genere los números primos hasta 37, lath prime.
El valor exacto deque genera todos los primos viene dado por la serie de convergencia rápida
dónde es el th prime, y es el producto de todos los primos menores que . Los más dígitos deque sabemos, más primos generará la ecuación ( 1 ). Por ejemplo, podemos usar 25 términos en la serie, usando los 25 primos menores que 100, para calcular la siguiente aproximación más precisa:
Esto tiene suficientes dígitos para que la ecuación ( 1 ) produzca nuevamente los 25 números primos menores que 100.
Al igual que con la fórmula de Mills y la fórmula de Wright anteriores, para generar una lista más larga de números primos, debemos comenzar conociendo más dígitos de la constante inicial, , que en este caso requiere una lista más larga de primos en su cálculo.
Fórmulas de Plouffe
En 2018, Simon Plouffe conjeturó un conjunto de fórmulas para números primos. De manera similar a la fórmula de Mills, tienen la forma
dónde es la función que se redondea al número entero más cercano. Por ejemplo, con y , esto da 113, 367, 1607, 10177, 102217 ... Usando y con un cierto número entre 0 y la mitad, Plouffe descubrió que podía generar una secuencia de 50 números primos probables (con alta probabilidad de ser primos). Es de suponer que existe un ε tal que esta fórmula dará una secuencia infinita de números primos reales. El número de dígitos comienza en 501 y aumenta aproximadamente un 1% cada vez. [11] [12]
Fórmulas primas y funciones polinomiales
Se sabe que no existe una función polinomial no constante P ( n ) con coeficientes enteros que evalúe a un número primo para todos los enteros n . La prueba es la siguiente: supongamos que tal polinomio existiera. Entonces P (1) se evaluaría a un primo p , entonces. Pero para cualquier entero k , asi mismo tampoco puede ser primo (ya que sería divisible por p ) a menos que fuera p . Pero la unica formapara todo k es si la función polinomial es constante. El mismo razonamiento muestra un resultado aún más fuerte: no existe una función polinomial no constante P ( n ) que evalúe a un número primo para casi todos los enteros n .
Euler notó por primera vez (en 1772) que el polinomio cuadrático
es primo para los 40 enteros n = 0, 1, 2, ..., 39, con los primos correspondientes 41, 43, 47, 53, 61, 71, ..., 1601. Las diferencias entre los términos son 2, 4 , 6, 8, 10 ... Para n = 40, produce un número cuadrado , 1681, que es igual a 41 × 41, el número compuesto más pequeño de esta fórmula para n ≥ 0. Si 41 divide n , divide P ( n ) también. Además, dado que P ( n ) se puede escribir como n ( n + 1) + 41, si 41 divide n + 1 en su lugar, también divide P ( n ). El fenómeno está relacionado con la espiral de Ulam , que también es implícitamente cuadrática, y el número de clase ; este polinomio está relacionado con el número de Heegner . Hay polinomios análogos para(los números de la suerte de Euler ), correspondientes a otros números de Heegner.
Dado un número entero positivo de S , que puede ser infinitamente muchos c de tal manera que la expresión n 2 + n + c es siempre primos entre sí a S . El número entero c puede ser negativo, en cuyo caso hay un retraso antes de que se produzcan los números primos.
Se sabe, según el teorema de Dirichlet sobre progresiones aritméticas , que las funciones polinomiales linealesproducir un número infinito de números primos, siempre que una y b son primos entre sí (aunque hay tal función asumirá valores primos para todos los valores de n ). Por otra parte, el Green-Tao teorema dice que para cualquier k existe un par de un y b , con la propiedad de quees primo para cualquier n desde 0 hasta k - 1. Sin embargo, a partir de 2020,[actualizar]el resultado más conocido de este tipo es para k = 27:
es primo para todo n de 0 a 26. [13] Ni siquiera se sabe si existe un polinomio univariante de grado al menos 2, que asume un número infinito de valores que son primos; ver la conjetura de Bunyakovsky .
Posible fórmula usando una relación de recurrencia
Otro generador principal se define por la relación de recurrencia
donde gcd ( x , y ) denota el máximo común divisor de x y y . La secuencia de diferencias a n +1 - a n comienza con 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, 47, 3, 1, 5, 3, ... (secuencia A132199 en la OEIS ). Rowland (2008) demostró que esta secuencia contiene solo unos y números primos. Sin embargo, no contiene todos los números primos, ya que los términos mcd ( n + 1, a n ) son siempre impares y, por lo tanto, nunca son iguales a 2. 587 es el primo más pequeño (distinto de 2) que no aparece en los primeros 10,000 resultados. que son diferentes de 1. Sin embargo, en el mismo artículo se conjeturaba que contenía todos los números primos impares, aunque es bastante ineficiente. [14]
Tenga en cuenta que hay un programa trivial que enumera todos y solo los números primos, así como los más eficientes , por lo que tales relaciones de recurrencia son más una cuestión de curiosidad que de uso práctico.
Ver también
- Teorema de los números primos
Referencias
- ^ Mackinnon, Nick (junio de 1987), "Fórmulas de números primos", The Mathematical Gazette , 71 (456): 113-114, doi : 10.2307 / 3616496 , JSTOR 3616496.
- ^ Jones, James P .; Sato, Daihachiro; Wada, Hideo; Wiens, Douglas (1976), "Representación diofántica del conjunto de números primos" , American Mathematical Monthly , Mathematical Association of America, 83 (6): 449–464, doi : 10.2307 / 2318339 , JSTOR 2318339 , archivado desde el original en 2012-02-24.
- ^ Matiyasevich, Yuri V. (1999), "Fórmulas para números primos" , en Tabachnikov, Serge (ed.), Kvant Selecta: Algebra and Analysis , II , American Mathematical Society , págs. 13-24, ISBN 978-0-8218-1915-9.
- ^ Jones, James P. (1982), "Ecuación diofántica universal", Journal of Symbolic Logic , 47 (3): 549–571, doi : 10.2307 / 2273588 , JSTOR 2273588.
- ^ Mills, WH (1947), "Una función de representación prima" (PDF) , Boletín de la Sociedad Matemática Estadounidense , 53 (6): 604, doi : 10.1090 / S0002-9904-1947-08849-2.
- ^ Tóth, László (2017), "A Variation on Mills-Like Prime-Representing Functions" (PDF) , Journal of Integer Sequences , 20 (17.9.8), arXiv : 1801.08014.
- ^ Elsholtz, Christian (2020). "Funciones representativas de prima incondicionales, siguiendo molinos". American Mathematical Monthly . Washington, DC: Asociación Matemática de América . 127 (7): 639–642. arXiv : 2004.01285 . doi : 10.1080 / 00029890.2020.1751560 . S2CID 214795216 .
- ^ EM Wright (1951). "Una función que representa a los primos". American Mathematical Monthly . 58 (9): 616–618. doi : 10.2307 / 2306356 . JSTOR 2306356 .
- ^ Baillie, Robert (5 de junio de 2017). "Cuarto primo de Wright". arXiv : 1705.09741v3 [ math.NT ].
- ^ Fridman, Dylan; Garbulsky, Juli; Glecer, Bruno; Grime, James; Tron Florentin, Massi (2019). "Una constante que representa a los primos". American Mathematical Monthly . Washington, DC: Asociación Matemática de América . 126 (1): 70–73. arXiv : 2010.15882 . doi : 10.1080 / 00029890.2019.1530554 . S2CID 127727922 .
- ^ Katie Steckles (26 de enero de 2019). "Fórmula récord del matemático puede generar 50 números primos" . Nuevo científico .
- ^ Simon Plouffe (2019). "Un conjunto de fórmulas para números primos". arXiv : 1901.01849 [ math.NT ]. A partir de enero de 2019, el número que da en el apéndice para el número 50 generado es en realidad el número 48.
- ^ Búsqueda AP27 de PrimeGrid, anuncio oficial , de PrimeGrid . El AP27 aparece en la "página Primes in Arithmetic Progression Records de Jens Kruse Andersen" .
- ^ Rowland, Eric S. (2008), "A Natural Prime-Generating Recurrence" , Journal of Integer Sequences , 11 (2): 08.2.8, arXiv : 0710.3217 , Bibcode : 2008JIntS..11 ... 28R.
Otras lecturas
- Regimbal, Stephen (1975), "Una fórmula explícita para el k-ésimo número primo", Revista de matemáticas, Asociación matemática de América, 48 (4): 230-232, doi : 10.2307 / 2690354 , JSTOR 2690354.
- Un Venugopalan. Fórmula para primos, primos gemelos, número de primos y número de primos gemelos . Actas de la Academia de Ciencias de la India — Ciencias Matemáticas, vol. 92, No 1, septiembre de 1983, págs. 49–52 erratas
enlaces externos
- Eric W. Weisstein , Prime Formulas ( polinomio generador de primos ) en MathWorld .