Fórmula para números primos

En teoría de números , una fórmula para números primos es aquella que produce números primos . Si bien existen fórmulas para calcular primos, su cálculo es muy lento en comparación con un algoritmo sencillo para encontrar números primos. Se conocen varias restricciones que determinan qué puede y qué no puede ser dicha "fórmula".

Una fórmula simple que produce todos los números primos, aunque en su mayoría intercalados con el número primo 2, es

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

para entero positivo${\displaystyle n}$, dónde${\displaystyle \lfloor \ \rfloor }$es la función piso , que redondea hacia abajo al entero más cercano. Los primeros valores de la función son 2, 2, 3, 2, 5, 2, 7, 2, 2, 2, 11... ^{[ 1 ]}

La fórmula funciona porque, según el teorema de Wilson ,${\displaystyle n+1}$es primo si y solo si${\displaystyle n!\equiv n\!\!\!\!\!{\pmod {n+1}}}$. Por lo tanto, cuando${\displaystyle n+1}$es primo, el primer factor del producto se convierte en uno, y la fórmula produce el número primo.${\displaystyle n+1}$. Pero cuando${\displaystyle n+1}$no es primo, el primer factor se convierte en cero y la fórmula produce el número primo 2. ^{[ 2 ]} Esta fórmula no es una forma eficiente de generar números primos porque evaluar${\displaystyle n!{\bmod {(}}n+1)}$requiere sobre${\displaystyle n-1}$multiplicaciones y reducciones módulo${\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${\displaystyle n}$el enésimo número primo${\displaystyle p_{n}}$. ^{[ 3 ]} Esta fórmula se reduce a ^{[ 4 ] [ 5 ]}

${\displaystyle p_{n}=1+\sum _{i=1}^{2^{n}}[\pi (i)<n];}$

es decir, define tautológicamente${\displaystyle p_{n}}$como el entero más pequeño${\displaystyle m}$para la cual la función de conteo de primos${\displaystyle \pi (m)}$es al menos${\displaystyle n}$Esta fórmula tampoco es eficiente. Además de la apariencia de${\displaystyle (j-1)!}$, calcula${\displaystyle p_{n}}$sumando${\displaystyle p_{n}}$copias de${\displaystyle 1}$; Por ejemplo,

${\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) ^{[ 6 ]} y Fórmulas para números primos de Underwood Dudley (1983) ^{[ 7 ]} ofrecen más información sobre la inutilidad de dichas fórmulas.

JP Jones dio en 1975 una fórmula más corta basada en el teorema de Wilson, utilizando${\displaystyle \mathrm {mod}}$como una función: ^{[ 8 ]}

${\displaystyle p_{n}=\sum _{i=0}^{n^{2}}\left(1\mathop {\dot {-}} \left(\left(\sum _{j=0}^{i}(j\mathop {\dot {-}} 1)!^{2}{\bmod {j}}\right)\mathop {\dot {-}} n\right)\right)}$.

Aquí,${\displaystyle \mathop {\dot {-}} }$es el operador monus , definido como${\displaystyle a\mathbin {\dot {-}} b=\max(ab,0)}$, y${\displaystyle x{\bmod {0}}}$se define como${\displaystyle x}$.

La noción de fracción continua puede utilizarse para definir la constante.${\displaystyle u_{1}=[p_{1},p_{2},p_{3},...]=2.31303673643...}$(secuencia A064442 en la OEIS ) a partir de la cual podemos recuperar la secuencia de números primos utilizando la siguiente relación de recurrencia.${\displaystyle u_{n+1}=(u_{n}-\lfloor u_{n}\rfloor )^{-1}}$y de ello se deduce que ${\displaystyle p_{n}=\lfloor u_{n}\rfloor }$.

Fridman et al. ^{[ 15 ]} propusieron una construcción alternativa . Dada la constante${\displaystyle f_{1}=2.920050977316\ldots }$(secuencia A249270 en el OEIS ) , para${\displaystyle n\geq 2}$, definir la secuencia$${\displaystyle f_{n}=\lfloor f_{n-1}\rfloor (f_{n-1}-\lfloor f_{n-1}\rfloor +1)}$$dónde${\displaystyle \left\lfloor \ \right\rfloor }$es la función piso . Entonces para${\displaystyle n\geq 1}$,${\displaystyle p_{n}=\lfloor f_{n}\rfloor }$La constante inicial${\displaystyle f_{1}=2.920050977316}$La información proporcionada en el artículo es suficientemente precisa para que la ecuación ( 1 ) genere los números primos hasta el 37, el duodécimo número primo.

El valor exacto de${\displaystyle f_{1}}$que genera todos los números primos viene dada por la serie de rápida convergencia

${\displaystyle f_{1}=\sum _{n=1}^{\infty }{\frac {p_{n}-1}{p_{n-1}\#}}={\frac {2-1}{1}}+{\frac {3-1}{2}}+{\frac {5-1}{2\cdot 3}}+{\frac {7-1}{2\cdot 3\cdot 5}}+\cdots ,}$

Cuantos más dígitos de${\displaystyle f_{1}}$que sabemos, cuantos más primos genere 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:

${\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.

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${\displaystyle n}$. ^{[ 16 ]} Si la hipótesis de Riemann es verdadera, entonces el más pequeño de tales${\displaystyle A}$tiene un valor de alrededor de 1,3063778838630806904686144926... (secuencia A051021 en el OEIS ) y se conoce como la constante de Mills . ^{[ 17 ]} Este valor da lugar a los números primos${\displaystyle \lfloor d_{1}\rfloor =2}$,${\displaystyle \lfloor d_{2}\rfloor =11}$,${\displaystyle \lfloor d_{3}\rfloor =1361}$, ... (secuencia A051254 en el OEIS ) . Se sabe muy poco sobre la constante${\displaystyle A}$Esta fórmula no tiene ningún valor práctico, porque no se conoce ninguna forma de calcular la constante sin encontrar primero números primos.

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

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

también es principal representante de${\displaystyle r>2.106\ldots }$. ^{[ 18 ]}

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

${\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${\displaystyle A=1.00536773279814724017\ldots }$, entonces${\displaystyle \left\lfloor A^{10^{10n}}\right\rfloor }$es primo para todos los enteros positivos${\displaystyle n}$. De manera similar, si${\displaystyle A=3.8249998073439146171615551375\ldots }$, entonces${\displaystyle \left\lfloor A^{3^{13n}}\right\rfloor }$es primo para todos los enteros positivos${\displaystyle n}$. ^{[ 19 ]}

Una fórmula generadora de números primos de crecimiento tetracional similar a la de Mills proviene de un teorema de E. M. Wright . Él 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 \lfloor g_{n}\rfloor =\left\lfloor 2^{\dots ^{2^{2^{\alpha }}}}\right\rfloor }$

es ideal para todos${\displaystyle n\geq 1}$. ^{[ 20 ]} Wright da los primeros siete decimales de dicha constante:${\displaystyle \alpha =1.9287800}$Este valor da lugar a los números primos.${\displaystyle \lfloor g_{1}\rfloor =\lfloor 2^{\alpha }\rfloor =3}$,${\displaystyle \lfloor g_{2}\rfloor =13}$, y${\displaystyle \lfloor g_{3}\rfloor =16381}$.${\displaystyle \lfloor g_{4}\rfloor }$es par , y por lo tanto no es primo. Sin embargo, con${\displaystyle \alpha =1.9287800+8.2843\cdot 10^{-4933}}$,${\displaystyle \lfloor g_{1}\rfloor }$,${\displaystyle \lfloor g_{2}\rfloor }$, y${\displaystyle \lfloor g_{3}\rfloor }$permanecen sin cambios, mientras que${\displaystyle \lfloor g_{4}\rfloor }$es un número primo con 4932 dígitos. ^{[ 21 ]} Esta secuencia de primos no se puede extender más allá de${\displaystyle \lfloor g_{4}\rfloor }$sin conocer más dígitos de${\displaystyle \alpha }$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.

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

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

dónde${\displaystyle \{\ \}}$es la función de redondeo al entero más cercano. Por ejemplo, con${\displaystyle a_{0}\approx 43.80468771580293481}$y${\displaystyle r=5/4}$, esto da 113, 367, 1607, 10177, 102217... (secuencia A323176 en el OEIS ) . Usando${\displaystyle a_{0}=10^{500}+961+\varepsilon }$y${\displaystyle r=1.01}$con${\displaystyle \varepsilon }$Con un cierto número entre 0 y 1/2, Plouffe descubrió 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. ^{[ 22 ] [ 23 ]}

Se sabe que no existe ninguna función polinómica no constante P ( n ) con coeficientes enteros que dé como resultado un número primo para todos los enteros n . La demostración es la siguiente: supongamos que existiera tal polinomio. Entonces P (1) daría como resultado un primo p , por lo que${\displaystyle P(1)\equiv 0{\pmod {p}}}$. Pero para cualquier entero k ,${\displaystyle P(1+kp)\equiv 0{\pmod {p}}}$también, así que${\displaystyle P(1+kp)}$tampoco puede ser primo (ya que sería divisible por p ) a menos que fuera p mismo. Pero la única manera${\displaystyle P(1+kp)=P(1)=p}$para todo 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 se evalúe a un número primo para casi todos los enteros n .

Euler fue el primero en notar (en 1772) que el polinomio cuadrático

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

es primo para los 40 enteros${\displaystyle n=0,1,2,\dots ,39}$con primos correspondientes${\displaystyle 41,43,47,53,61,71,\dots ,1601}$Las diferencias entre los términos son${\displaystyle 2,4,6,8,10\dots }$Para${\displaystyle n=40}$, produce un número cuadrado ,${\displaystyle 1681}$, que es igual a${\displaystyle 41\times 41}$, el número compuesto más pequeño para esta fórmula para${\displaystyle n\geq 0}$. Si${\displaystyle 41}$divide${\displaystyle n}$, divide${\displaystyle P(n)}$también. Además, dado que${\displaystyle P(n)}$se puede escribir como${\displaystyle n(n+1)+41}$, si${\displaystyle 41}$divide${\displaystyle n+1}$En cambio, también divide${\displaystyle 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.${\displaystyle 163=4\cdot 41-1}$. Existen polinomios análogos para${\displaystyle p=2,3,5,11{\text{ and }}17}$(los números de la suerte de Euler ), que corresponden a otros números de Heegner.

Dado un número entero positivo${\displaystyle S}$, puede haber infinitas${\displaystyle c}$de tal manera que la expresión${\displaystyle n^{2}+n+c}$siempre es coprimo con${\displaystyle S}$. El número entero${\displaystyle c}$puede ser negativo, en cuyo caso hay un retraso antes de que se produzcan los números primos.

De manera similar, otros polinomios (de grado superior) producen secuencias finitas de números primos. ^{[ 24 ]} En 2010, Dress y Landreau encontraron el siguiente polinomio que representa un récord de 58 primos en valores consecutivos: ^{[ 25 ] [ 26 ]}$${\displaystyle Q(n)={\frac {1}{72}}n^{6}-{\frac {5}{24}}n^{5}-{\frac {1493}{72}}n^{4}+{\frac {1027}{8}}n^{3}+{\frac {100471}{18}}n^{2}-{\frac {11971}{6}}n-57347}$$Más precisamente,${\displaystyle |Q(n)|}$es ideal para${\displaystyle n}$con valores que van desde -42 hasta 15.

Se sabe, basándose en el teorema de Dirichlet sobre progresiones aritméticas , que las funciones polinómicas lineales${\displaystyle L(n)=an+b}$producir infinitos primos siempre que${\displaystyle a}$y${\displaystyle b}$son relativamente primos (aunque ninguna función de este tipo asumirá valores primos para todos los valores de${\displaystyle n}$). Además, el teorema de Green-Tao dice que para cualquier${\displaystyle k}$Existe un par de a y b , con la propiedad de que${\displaystyle L(n)=an+b}$es ideal para cualquier${\displaystyle n}$desde 0 hasta${\displaystyle k-1}$Sin embargo, a partir de 2020,El resultado más conocido de este tipo es para${\displaystyle k=27}$:

${\displaystyle 224584605939537911+18135696597948930n}$

es ideal para todos${\displaystyle n}$de 0 a 26. ^{[ 27 ]} Ni siquiera se sabe si existe un polinomio univariado de grado al menos 2 que tome un número infinito de valores primos; véase la conjetura de Bunyakovsky .

Otro generador primo se define mediante la relación de recurrencia.

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

dónde${\displaystyle \gcd }$denota la función máximo común divisor . La secuencia de diferencias${\displaystyle 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, 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${\displaystyle \gcd(n+1,a_{n})}$son siempre impares y, por lo tanto, nunca iguales a 2. El mismo artículo conjetura que la secuencia contiene todos los primos impares: de hecho, 587 es el primo impar más pequeño que no aparece en los primeros 10 000 resultados distintos de 1. ^{[ 28 ]}

Esta recurrencia es bastante ineficiente. En perspectiva, es trivial escribir un algoritmo para generar todos los números primos (a partir de la definición), y se conocen muchos algoritmos más eficientes . Por lo tanto, tales relaciones de recurrencia son más una cuestión de curiosidad que de utilidad práctica.

Debido a que el conjunto de números primos es un conjunto computacionalmente 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.${\displaystyle a,b,...,z}$, de tal manera que un número dado${\displaystyle k+2}$es primo si y solo si ese sistema tiene una solución en enteros no negativos: ^{[ 29 ]}

${\displaystyle {\begin{aligned}\alpha _{0}&=wz+h+j-q=0\\\alpha _{1}&=(gk+2g+k+1)(h+j)+h-z=0\\\alpha _{2}&=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}=0\\\alpha _{3}&=2n+p+q+z-e=0\\\alpha _{4}&=e^{3}(e+2)(a+1)^{2}+1-o^{2}=0\\\alpha _{5}&=(a^{2}-1)y^{2}+1-x^{2}=0\\\alpha _{6}&=16r^{2}y^{4}(a^{2}-1)+1-u^{2}=0\\\alpha _{7}&=n+\ell +v-y=0\\\alpha _{8}&=(a^{2}-1)\ell ^{2}+1-m^{2}=0\\\alpha _{9}&=ai+k+1-\ell -i=0\\\alpha _{10}&=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}=0\\\alpha _{11}&=p+\ell (a-n-1)+b(2an+2a-n^{2}-2n-2)-m=0\\\alpha _{12}&=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x=0\\\alpha _{13}&=z+p\ell (a-p)+t(2ap-p^{2}-1)-pm=0\end{aligned}}}$

Las 14 ecuaciones${\displaystyle \alpha _{0},\dots ,\alpha _{13}}$Se puede utilizar para producir una desigualdad polinómica generadora de números primos en 26 variables:

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

es una desigualdad polinómica en 26 variables, y el conjunto de números primos es idéntico al conjunto de valores positivos que toma el lado izquierdo como las variables${\displaystyle a,b,...,z}$abarca los números enteros no negativos.

Un teorema general de Matiyasevich afirma que si un conjunto se define mediante un sistema de ecuaciones diofánticas, también puede definirse mediante un sistema de ecuaciones diofánticas con solo 9 variables. ^{[ 30 ]} Por lo tanto, existe una desigualdad polinómica generadora de números primos como la 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 4, pero con 58 variables. ^{[ 31 ]}

• Teorema de los números primos

• 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 

• Venugopalan, A (septiembre de 1983), "Fórmula para primos, primos gemelos, número de primos y número de primos gemelos", Actas de la Academia India de Ciencias—Ciencias Matemáticas , 92 (1): 49– 52, doi : 10.1007/BF02866907( erratas )

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