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 números primos es una fórmula que genera los números primos , exactamente y sin excepción. Existen fórmulas para calcular números primos, sin embargo, son computacionalmente muy lentas. Se conocen varias limitaciones que muestran lo que esa "fórmula" puede y no puede ser.

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 entero positivo , donde está la función suelo , que se redondea hacia abajo al entero más cercano. Según el teorema de Wilson , es primo si y sólo 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 vuelve 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 multiplicaciones y reducciones de 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 décimo número primo . ^[2] Esta fórmula se reduce a ^{[3] [4]} ; es decir, se 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 apariencia de , 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 Formulas for Primes de Underwood Dudley (1983) ^[6] tienen más discusiones sobre la inutilidad de tales fórmulas.

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

Debido a que el conjunto de números primos es un conjunto computable enumerable , según el teorema de Matiyasevich , se puede obtener a partir de un sistema de ecuaciones diofánticas . Jones y cols. (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 sólo 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 polinómica 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 polinómica 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 abarcan 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 definirse mediante un sistema de ecuaciones diofánticas en sólo 9 variables. ^[8] Por lo tanto, existe un polinomio generador de primos como el anterior con solo 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 en 58 variables. ^[9]

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

${\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 números enteros positivos n . ^[10] Si la hipótesis de Riemann es cierta, entonces la A más pequeñ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 números 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 se conoce ninguna manera de calcular la constante sin encontrar números 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}$

Tenga en cuenta que no hay nada especial en la función suelo de 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 representante primo de . ^[12] ${\displaystyle r>2.106\ldots }$

En el caso , el valor de la constante comienza con 1.24055470525201424067... Los primeros números 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 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 primordial para todos . ^[14] Wright da los primeros siete decimales de dicha constante: . Este valor da lugar a los números primos , y . es par y, por tanto, no es primo. Sin embargo, con , , y no cambian, mientras que es un número primo con 4932 dígitos. ^[15] Esta secuencia de números 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 números 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 el OEIS ), para , define la secuencia ${\displaystyle f_{1}=2.920050977316\ldots }$ ${\displaystyle n\geq 2}$

¿Dónde está la función del suelo ? Entonces, para , es igual al enésimo primo: , , , 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 enésimo primo. ${\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 de que genera todos los números primos viene dado por la serie rápidamente convergente ${\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 ésimo primo y es el producto de todos los primos menores que . Cuantos más dígitos sepamos, más primos generará la ecuación ( 1 ). Por ejemplo, podemos usar 25 términos de la serie, usando 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 anterior, para generar una lista más larga de números primos, debemos comenzar por conocer 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\}}$

¿Dónde está la función que redondea al número entero más cercano? Por ejemplo, con y , esto da 113, 367, 1607, 10177, 102217... (secuencia A323176 en el OEIS ). Usando y con un número determinado 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). 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 primas y funciones polinomiales.

Se sabe que no existe una función polinómica no constante P ( n ) con coeficientes enteros que evalúe como un número primo para todos los números enteros n . La prueba es la siguiente: supongamos que tal polinomio existiera. Entonces P (1) se evaluaría como un primo p , entonces . Pero para cualquier número entero k , tampoco puede ser primo (ya que sería divisible por p ) a menos que fuera p en sí. Pero la única forma para todo k es si la función polinómica es constante. El mismo razonamiento muestra un resultado aún más sólido: no existe una función polinómica no constante P ( n ) que evalúe como un número primo para casi todos los números 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 números 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 para esta fórmula para n ≥ 0. Si 41 divide a n , divide a P ( n ) también. Además, dado que P ( n ) se puede escribir como n ( n + 1) + 41, si 41 divide a n + 1, 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 coprima de 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, basándose en el teorema de Dirichlet sobre progresiones aritméticas , que las funciones polinomiales lineales producen infinitos números primos siempre que a y b sean primos relativos (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 partir 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 univariado de grado al menos 2, que asuma un número infinito de valores primos; ver conjetura de Bunyakovsky .

Posible fórmula usando una relación de recurrencia

Otro generador de primos está definido 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, 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 , 1, 47, 3, 1, 5, 3, ... (secuencia A132199 en el OEIS ). Rowland (2008) demostró que esta secuencia contiene sólo unos y números primos. Sin embargo, no contiene todos los números primos, ya que los términos mcd( n + 1, a _n ) siempre son impares y, por lo tanto, nunca son iguales a 2. 587 es el primo más pequeño (aparte 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 contiene todos los números primos impares, aunque es bastante ineficiente. ^[20]

Tenga 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.

Ver 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 número primo número", The Mathematical Gazette , 48 (366): 413–415, doi :10.2307/3611701, JSTOR  3611701, S2CID  126149459 ${\displaystyle n}$.
3. Neill, tuneladora; 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 en 2012-02-24.
8. Matiyasevich, Yuri V. (1999), "Fórmulas para números primos", en Tabachnikov, Serge (ed.), Kvant Selecta: Álgebra y análisis , vol. II, Sociedad Estadounidense de Matemáticas , 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 de representación prima" (PDF) , Boletín de la Sociedad Estadounidense de Matemáticas , 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 funciones de representación primaria tipo molino" (PDF) , Journal of Integer Sequences , 20 (17.9.8), arXiv : 1801.08014.
13. Elsholtz, Christian (2020), "Funciones de representación prima incondicionales, 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 de representación prima", American Mathematical Monthly , 58 (9): 616–618, doi :10.2307/2306356, JSTOR  2306356
15. Baillie, Robert (5 de junio de 2017), "Wright's Fourth Prime", arXiv : 1705.09741v3 [math.NT]
16. Fridman, Dylan; Garbulsky, Julio; Glécer, Bruno; Suciedad, James; Tron Florentin, Massi (2019), "Una constante de representación prima", American Mathematical Monthly , 126 (1), Washington, DC: Mathematical Association of America : 70–73, arXiv : 2010.15882 , doi : 10.1080/00029890.2019.1530554, S2CID  127727922
17. Steckles, Katie (26 de enero de 2019), "La fórmula récord 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 proporciona en el apéndice para el número 50 generado es en realidad el 48.
19. Búsqueda AP27 de PrimeGrid, anuncio oficial, de PrimeGrid . El AP27 aparece en la "página de registros de números primos en progresión aritmética de Jens Kruse Andersen".
20. Rowland, Eric S. (2008), "Una recurrencia natural generadora de primos", 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 , 48 ​​(4), Asociación Matemática de América: 230–232, doi :10.2307/2690354, JSTOR  2690354.
• Un Venugopalan. Fórmula para números 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, n.º 1, septiembre de 1983, págs. 49–52 erratas

enlaces externos

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