Fórmula para números primos

Fórmula cuyos valores son los números primos

En teoría de números , una fórmula para los números primos es una fórmula que genera los números primos , de manera exacta y sin excepción. Existen fórmulas para calcular los números primos, pero su procesamiento es muy lento. Se conocen una serie de restricciones que muestran lo que puede y no puede ser una "fórmula" de este tipo.

Fórmulas basadas en el teorema de Wilson

Una fórmula sencilla es

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

para un entero positivo , donde es la función base , que redondea hacia abajo al 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 cuando no 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 la evaluación requiere aproximadamente multiplicaciones y reducciones 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}$

En 1964, Willans dio la 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 el ésimo número primo . ^[2] Esta fórmula se reduce a ^{[3] [4]} ; es decir, define tautológicamente como el entero más pequeño m para el cual la función de conteo de primos es al menos n . Esta fórmula tampoco es eficiente. Además de la aparición de , se calcula sumando copias de ; por ejemplo, . ${\displaystyle n}$ ${\displaystyle p_{n}}$ ${\displaystyle p_{n}=1+\sum _{i=1}^{2^{n}}[\pi (i)<n]}$ ${\displaystyle p_{n}}$ ${\displaystyle \pi (m)}$ ${\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}$

Los artículos ¿Qué es una respuesta? de Herbert Wilf (1982) ^[5] y Fórmulas para números primos de Underwood Dudley (1983) ^[6] contienen una discusión más detallada sobre la inutilidad de dichas fórmulas.

Fórmula basada en un sistema de ecuaciones diofánticas

Como el conjunto de primos es un conjunto computablemente enumerable , por el teorema de Matiyasevich , se puede obtener a partir de un sistema de ecuaciones diofánticas . Jones et al. (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 enteros no negativos: ^[7]

${\displaystyle \alpha _{0}=wz+h+j-q=0}$

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

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

${\displaystyle \alpha _{3}=2n+p+q+z-e=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 +v-y=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 (a-n-1)+b(2an+2a-n^{2}-2n-2)-m=0}$

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

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

Las 14 ecuaciones α ₀ , …, α ₁₃ se pueden utilizar para producir una desigualdad polinomial generadora de primos en 26 variables:

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

Eso es,

${\displaystyle {\begin{aligned}&(k+2)(1-{}\\[6pt]&[wz+h+j-q]^{2}-{}\\[6pt]&[(gk+2g+k+1)(h+j)+h-z]^{2}-{}\\[6pt]&[16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}]^{2}-{}\\[6pt]&[2n+p+q+z-e]^{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 +v-y]^{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 (a-n-1)+b(2an+2a-n^{2}-2n-2)-m]^{2}-{}\\[6pt]&[q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x]^{2}-{}\\[6pt]&[z+p\ell (a-p)+t(2ap-p^{2}-1)-pm]^{2})\\[6pt]&>0\end{aligned}}}$

es una desigualdad polinomial en 26 variables, y el conjunto de números primos es idéntico al conjunto de valores positivos que toma el lado izquierdo a medida que las variables a , b , …, z abarcan los números 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 definirse por un sistema de ecuaciones diofánticas con sólo 9 variables. ^[8] Por lo tanto, existe un polinomio generador de primos como el anterior con sólo 10 variables. Sin embargo, su grado es grande (del orden de 10 ⁴⁵ ). Por otro lado, también existe un conjunto de ecuaciones de grado sólo 4, pero con 58 variables. ^[9]

La fórmula de Mills

La primera fórmula de este tipo conocida fue establecida por WH Mills (1947), quien demostró que existe un número real A tal que, si

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

entonces

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

es un número primo para todos los enteros positivos n . ^[10] Si la hipótesis de Riemann es verdadera, entonces el más pequeño de tales A tiene un valor de alrededor de 1.3063778838630806904686144926... (secuencia A051021 en la OEIS ) y se conoce como constante de Mills . ^[11] 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 hay forma conocida de calcular la constante sin encontrar primos en primer 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}$

Nótese que no hay nada especial en la función de suelo en la fórmula. Tóth demostró que también existe una constante tal que ${\displaystyle B}$

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

también es el representante primo de . ^[12] ${\displaystyle r>2.106\ldots }$

En el caso , el valor de la constante comienza con 1,24055470525201424067... Los primeros primos generados son: ${\displaystyle r=3}$ ${\displaystyle B}$

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

${\displaystyle 176199995814327287356671209104585864397055039072110696028654438846269,\ldots }$

Sin asumir la hipótesis de Riemann, Elsholtz desarrolló varias funciones de representación de números primos similares a las de Mills. Por ejemplo, si , entonces es primo para todos los números enteros positivos . De manera similar, si , entonces es primo para todos los números enteros positivos . ^[13] ${\displaystyle A=1.00536773279814724017\ldots }$ ${\displaystyle \left\lfloor A^{10^{10n}}\right\rfloor }$ ${\displaystyle n}$ ${\displaystyle A=3.8249998073439146171615551375\ldots }$ ${\displaystyle \left\lfloor A^{3^{13n}}\right\rfloor }$ ${\displaystyle n}$

La fórmula de Wright

Otra fórmula generadora de primos de crecimiento tetracional similar a la de Mills proviene de un teorema de EM Wright . Demostró que existe un número real α tal que, si

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

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

entonces

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

es primo para todo . ^[14] Wright da los primeros siete decimales de dicha constante: . Este valor da lugar a los primos , , y . es par , y por lo tanto no es primo. Sin embargo, con , , , y no cambian, mientras que es un primo con 4932 dígitos. ^[15] Esta secuencia de primos no se puede extender más allá sin conocer más dígitos de . Al igual que la fórmula de Mills, y por las mismas razones, la fórmula de Wright no se puede utilizar 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 }$

Una función que representa todos los números primos

Dada la constante (secuencia A249270 en la OEIS ), para , defina la secuencia ${\displaystyle f_{1}=2.920050977316\ldots }$ ${\displaystyle n\geq 2}$

donde es la función piso . Entonces, para , es igual al primo n°: , , , etc. ^[16] La constante inicial dada en el artículo es lo suficientemente precisa para que la ecuación ( 1 ) genere los primos hasta 37, el primo n°. ${\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}$

El valor exacto que genera todos los números primos viene dado por la serie de convergencia 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 ,}$

donde es el primo n° 1 y es el producto de todos los primos menores que . Cuantos más dígitos de n° 1 conozcamos, más primos generará la ecuación ( 1 ). Por ejemplo, podemos utilizar 25 términos de la serie, utilizando los 25 primos menores que 100, para calcular la siguiente aproximación más precisa: ${\displaystyle p_{n}}$ ${\displaystyle n}$ ${\displaystyle P_{n}}$ ${\displaystyle p_{n}}$ ${\displaystyle f_{1}}$

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

Esto tiene suficientes dígitos para que la ecuación ( 1 ) produzca nuevamente los 25 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, , lo que en este caso requiere una lista más larga de números primos en su cálculo. ${\displaystyle f_{1}}$

Las fórmulas de Plouffe

En 2018, Simon Plouffe conjeturó un conjunto de fórmulas para los números primos. De manera similar a la fórmula de Mills, tienen la forma

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

donde es la función que redondea al entero más cercano. Por ejemplo, con y , esto da 113, 367, 1607, 10177, 102217... (secuencia A323176 en la OEIS ). Usando y con un cierto número entre 0 y un medio, Plouffe encontró que podía generar una secuencia de 50 primos probables (con alta probabilidad de ser primos). Presumiblemente 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. ^{[17] [18]} ${\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 primos y funciones polinómicas

Se sabe que no existe ninguna función polinómica no constante P ( n ) con coeficientes enteros que evalúe un número primo para todos los enteros n . La prueba es la siguiente: supongamos que existiera tal polinomio. Entonces P (1) evaluaría un primo p , por lo tanto . Pero para cualquier entero k , también, por lo que no puede ser primo (ya que sería divisible por p ) a menos que fuera p mismo. Pero la única manera para todos los k es si la función polinómica es constante. El mismo razonamiento muestra un resultado aún más fuerte: no existe ninguna función polinómica no constante P ( n ) que evalúe un número primo para casi todos los enteros 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 notó por primera vez (en 1772) que el polinomio cuadrático

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

es primo para los 40 enteros n = 0, 1, 2, ..., 39, con 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 para esta fórmula para n ≥ 0. Si 41 divide a n , también divide a P ( n ). Además, dado que P ( n ) se puede escribir como n ( n + 1) + 41, si 41 divide a n + 1 en cambio, también divide a 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 . Existen polinomios análogos para (los números de la suerte de Euler ), correspondientes a otros números de Heegner. ${\displaystyle 163=4\cdot 41-1}$ ${\displaystyle p=2,3,5,11{\text{ and }}17}$

Dado un entero positivo S , puede haber infinitos c tales que la expresión n ² + n + c siempre sea coprimo con S . El entero c puede ser negativo, en cuyo caso hay un retraso antes de que se produzcan primos.

Se sabe, a partir del teorema de Dirichlet sobre progresiones aritméticas , que las funciones polinómicas lineales producen infinitos números primos siempre que a y b sean primos entre sí (aunque ninguna función de este tipo asumirá valores primos para todos los valores de n ). Además, el teorema de Green-Tao dice que para cualquier k existe un par de a y b , con la propiedad de que es primo para cualquier n desde 0 hasta k  − 1. Sin embargo, a fecha de 2020, el resultado más conocido de este tipo es para k = 27: ${\displaystyle L(n)=an+b}$ ${\displaystyle L(n)=an+b}$^[update]

${\displaystyle 224584605939537911+18135696597948930n}$

es primo para todo n desde 0 hasta 26. ^[19] Ni siquiera se sabe si existe un polinomio univariante de grado al menos 2, que asuma un número infinito de valores que sean primos; véase la conjetura de Bunyakovsky .

Posible fórmula utilizando una relación de recurrencia

Otro generador primo se define por la relación de recurrencia

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

donde mcd( x , y ) denota el máximo común divisor de x e 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, 23, 3, 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 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 conjeturó que contenía todos los primos impares, aunque es bastante ineficiente. ^[20]

Téngase en cuenta que existe un programa trivial que enumera todos y sólo los números primos, así como los más eficientes , por lo que dichas relaciones de recurrencia son más una cuestión de curiosidad que de uso práctico.

Véase también

• Teorema de los números primos

Referencias

1. Mackinnon, Nick (junio de 1987), "Fórmulas de números primos", The Mathematical Gazette , 71 (456): 113–114, doi :10.2307/3616496, JSTOR  3616496, S2CID  171537609.
2. Willans, CP (diciembre de 1964), "Sobre fórmulas para el ésimo número primo", The Mathematical Gazette , 48 (366): 413–415, doi :10.2307/3611701, JSTOR  3611701, S2CID  126149459 ${\displaystyle n}$.
3. Neill, TBM; Singer, M. (octubre de 1965), "Al editor, The Mathematical Gazette ", The Mathematical Gazette , 49 (369): 303–303, doi :10.2307/3612863, JSTOR  3612863
4. Goodstein, RL; Wormell, CP (febrero de 1967), "Fórmulas para números primos", The Mathematical Gazette , 51 (375): 35–38, doi :10.2307/3613607, JSTOR  3613607
5. Wilf, Herbert S. (1982), "¿Qué es una respuesta?", The American Mathematical Monthly , 89 (5): 289–292, doi :10.2307/2321713, JSTOR  2321713, MR  0653502
6. Dudley, Underwood (1983), "Fórmulas para números primos", Mathematics Magazine , 56 (1): 17–22, doi :10.2307/2690261, JSTOR  2690261, MR  0692169
7. Jones, James P.; Sato, Daihachiro; Wada, Hideo; Wiens, Douglas (1976), "Representación diofántica del conjunto de números primos", American Mathematical Monthly , 83 (6), Mathematical Association of America: 449–464, doi :10.2307/2318339, JSTOR  2318339, archivado desde el original el 24 de febrero de 2012.
8. Matiyasevich, Yuri V. (1999), "Fórmulas para números primos", en Tabachnikov, Serge (ed.), Kvant Selecta: Algebra and Analysis , vol. II, American Mathematical Society , págs. 13-24, ISBN 978-0-8218-1915-9.
9. Jones, James P. (1982), "Ecuación diofántica universal", Journal of Symbolic Logic , 47 (3): 549–571, ​​doi :10.2307/2273588, JSTOR  2273588, S2CID  11148823.
10. Mills, WH (1947), "Una función que representa primos" (PDF) , Boletín de la Sociedad Matemática Americana , 53 (6): 604, doi : 10.1090/S0002-9904-1947-08849-2.
11. Caldwell, Chris K.; Cheng, Yuanyou (2005), "Determinación de la constante de Mills y una nota sobre el problema de Honaker", Journal of Integer Sequences , 8 , Artículo 05.4.1.
12. Tóth, László (2017), "Una variación de las funciones de representación de números primos similares a Mills" (PDF) , Journal of Integer Sequences , 20 (17.9.8), arXiv : 1801.08014.
13. Elsholtz, Christian (2020), "Funciones incondicionales que representan números primos, siguiendo a Mills", American Mathematical Monthly , 127 (7), Washington, DC: Mathematical Association of America : 639–642, arXiv : 2004.01285 , doi :10.1080/00029890.2020.1751560, S2CID  214795216
14. EM Wright (1951), "Una función que representa números primos", American Mathematical Monthly , 58 (9): 616–618, doi :10.2307/2306356, JSTOR  2306356
15. Baillie, Robert (5 de junio de 2017), "El cuarto primo de Wright", arXiv : 1705.09741v3 [math.NT]
16. Fridman, Dylan; Garbulsky, Juli; Glecer, Bruno; Grime, James; Tron Florentin, Massi (2019), "Una constante que representa a los primos", American Mathematical Monthly , 126 (1), Washington, DC: Asociación Matemática de América : 70–73, arXiv : 2010.15882 , doi :10.1080/00029890.2019.1530554, S2CID  127727922
17. Steckles, Katie (26 de enero de 2019), "La fórmula que bate récords de un matemático puede generar 50 números primos", New Scientist
18. 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 48.
19. Búsqueda de AP27 de PrimeGrid, anuncio oficial de PrimeGrid . El AP27 aparece en la "página de registros de primos en progresión aritmética de Jens Kruse Andersen".
20. Rowland, Eric S. (2008), "Una recurrencia generadora de números primos natural", Journal of Integer Sequences , 11 (2): 08.2.8, arXiv : 0710.3217 , Bibcode :2008JIntS..11...28R.

Lectura adicional

• Regimbal, Stephen (1975), "Una fórmula explícita para el k-ésimo número primo", Mathematics Magazine , 48 (4), Mathematical Association of America: 230–232, doi :10.2307/2690354, JSTOR  2690354.
• A Venugopalan. Fórmula para números primos, primos gemelos, número de primos y número de primos gemelos . Actas de la Academia India de Ciencias—Ciencias Matemáticas, vol. 92, n.º 1, septiembre de 1983, págs. 49–52 erratas

Enlaces externos

• Weisstein, Eric W. , "Fórmulas primos" ("Polinomio generador de primos") en MathWorld .