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 , donde 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 ]}${\displaystyle n}$${\displaystyle \lfloor \ \rfloor }$

La fórmula funciona porque, según 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. ^{[ 2 ]} Esta fórmula no es una forma eficiente de generar números primos porque su evaluación requiere aproximadamente multiplicaciones y reducciones módulo . ${\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 . ^{[ 3 ]} Esta fórmula se reduce a ^{[ 4 ] [ 5 ]}${\displaystyle n}$${\displaystyle p_{n}}$

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

es decir, define tautológicamente como el entero más pequeño para el cual la función de conteo de primos es al menos . Esta fórmula tampoco es eficiente. Además de la apariencia de , calcula sumando copias de ; por ejemplo, ${\displaystyle p_{n}}$${\displaystyle m}$${\displaystyle \pi (m)}$${\displaystyle n}$${\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) ^{[ 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, usando como función: ^{[ 8 ]}${\displaystyle \mathrm {mod}}$

${\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í, es el operador monus , definido como , y se define como . ${\displaystyle \mathop {\dot {-}} }$${\displaystyle a\mathbin {\dot {-}} b=\max(ab,0)}$${\displaystyle x{\bmod {0}}}$${\displaystyle x}$

En 1971, JM Gandhi demostró que donde , es la función de Möbius y pasa por todos los divisores de , el primordio de . ^{[ 9 ] [ 10 ] [ 11 ]} Esta fórmula debe verse como una relación de recurrencia para los números primos, expresada en términos de . $${\displaystyle p_{n}=\left\lfloor 1-\log _{2}\left(s_{n-1}-{\frac {1}{2}}\right)\right\rfloor ,}$$${\displaystyle s_{n}=\sum _{d|p_{n}\#}{\frac {\mu (d)}{2^{d}-1}}}$${\displaystyle \mu }$${\displaystyle d}$${\displaystyle p_{n}\#}$${\displaystyle p_{n}}$${\displaystyle p_{n}}$${\displaystyle p_{1},p_{2},\dots ,p_{n-1}}$

Esta expresión dada por Gandhi resulta de la aplicación de una criba de Eratóstenes modificada que opera sobre los exponentes de las potencias de en la suma después de pasos. Más precisamente, Gandhi demostró que , donde los puntos representan términos con exponentes crecientes mayores que . ^{[ 11 ]} Existen recurrencias análogas donde el proceso se realiza en una base distinta de . ^{[ 12 ] [ 13 ]}${\displaystyle s_{n}}$${\displaystyle {\frac {1}{2}}}$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{2^{k}}}}$${\displaystyle n}$${\displaystyle s_{n}={\frac {1}{2^{1}}}+{\frac {1}{2^{p_{n+1}}}}+\dots }$${\displaystyle p_{n+1}}$${\displaystyle b}$${\displaystyle 2}$

En 2025 se publicó una expresión más sencilla para: ${\displaystyle s_{n}}$

${\displaystyle s_{n}=\left\{{\frac {1}{2^{p_{n}\#}-1}}\prod _{i=1}^{n}{\frac {2^{p_{n}\#}-2^{p_{n}\#/p_{i}}}{2^{p_{n}\#/p_{i}}-1}}\right\}}$, donde denota la parte fraccionaria de . ^{[ 14 ]}${\displaystyle \{x\}}$${\displaystyle x}$

Se basa en un uso más ingenioso de la criba de Eratóstenes mediante el teorema chino del resto .

Inspirado por la demostración de Gandhi, Golomb demostró la siguiente recurrencia ^{[ 12 ]} donde denota la función zeta de Riemann . Se basa en el producto de Euler para . $${\displaystyle p_{n}=\lim _{s\to \infty }\left(\zeta (s)\prod _{k=1}^{n-1}(1-p_{k}^{-s})-1\right)^{-{\frac {1}{s}}},}$$${\displaystyle \zeta }$${\displaystyle \zeta }$

La noción de fracción continua se puede utilizar para definir la constante (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 , y de ello se deduce que . ${\displaystyle u_{1}=[p_{1},p_{2},p_{3},...]=2.31303673643...}$${\displaystyle u_{n+1}=(u_{n}-\lfloor u_{n}\rfloor )^{-1}}$${\displaystyle p_{n}=\lfloor u_{n}\rfloor }$

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

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-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 conozcamos, más primos generará la ecuación ( 1 ). Por ejemplo, podemos usar 25 términos de la serie, utilizando los 25 primos menores que 100, para calcular la siguiente aproximación más precisa:${\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.

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

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

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

también es primo representativo para . ^{[ 18 ]}${\displaystyle r>2.106\ldots }$

En este 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 que representan números primos, similares a las de Mills. Por ejemplo, si , entonces es primo para todos los enteros positivos . De manera similar, si , entonces es primo para todos los enteros positivos . ^{[ 19 ]}${\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}$

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 primo para todos . ^{[ 20 ]} 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 permanecen sin cambios, mientras que es un primo con 4932 dígitos. ^{[ 21 ]} Esta secuencia de primos no puede extenderse más allá de 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 puede usarse para encontrar primos. ${\displaystyle n\geq 1}$${\displaystyle \alpha =1.9287800}$${\displaystyle \lfloor g_{1}\rfloor =\lfloor 2^{\alpha }\rfloor =3}$${\displaystyle \lfloor g_{2}\rfloor =13}$${\displaystyle \lfloor g_{3}\rfloor =16381}$${\displaystyle \lfloor g_{4}\rfloor }$${\displaystyle \alpha =1.9287800+8.2843\cdot 10^{-4933}}$${\displaystyle \lfloor g_{1}\rfloor }$${\displaystyle \lfloor g_{2}\rfloor }$${\displaystyle \lfloor g_{3}\rfloor }$${\displaystyle \lfloor g_{4}\rfloor }$${\displaystyle \lfloor g_{4}\rfloor }$${\displaystyle \alpha }$

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\}}$

donde es la función de redondeo 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 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 ]}${\displaystyle \{\ \}}$${\displaystyle a_{0}\approx 43.80468771580293481}$${\displaystyle r=5/4}$${\displaystyle a_{0}=10^{500}+961+\varepsilon }$${\displaystyle r=1.01}$${\displaystyle \varepsilon }$

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 prueba es la siguiente: supongamos que existiera tal polinomio. Entonces P (1) daría como resultado un primo p , por lo que . 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 forma 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 dé como resultado 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 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 con primos correspondientes . Las diferencias entre los términos son Para , produce un número cuadrado , , que es igual a , el número compuesto más pequeño para esta fórmula para . Si divide a , también divide a . Además, dado que se puede escribir como , si divide en su lugar, también divide a . 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 ), que corresponden a otros números de Heegner. ${\displaystyle n=0,1,2,\dots ,39}$${\displaystyle 41,43,47,53,61,71,\dots ,1601}$${\displaystyle 2,4,6,8,10\dots }$${\displaystyle n=40}$${\displaystyle 1681}$${\displaystyle 41\times 41}$${\displaystyle n\geq 0}$${\displaystyle 41}$${\displaystyle n}$${\displaystyle P(n)}$${\displaystyle P(n)}$${\displaystyle n(n+1)+41}$${\displaystyle 41}$${\displaystyle n+1}$${\displaystyle P(n)}$${\displaystyle 163=4\cdot 41-1}$${\displaystyle p=2,3,5,11{\text{ and }}17}$

Dado un entero positivo , puede haber infinitos tales que la expresión sea siempre coprima con . El entero puede ser negativo, en cuyo caso hay un retraso antes de que se produzcan primos. ${\displaystyle S}$${\displaystyle c}$${\displaystyle n^{2}+n+c}$${\displaystyle S}$${\displaystyle c}$

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 ]} Más precisamente, es primo para valores que van de -42 a 15. $${\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}$$${\displaystyle |Q(n)|}$${\displaystyle n}$

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

${\displaystyle 224584605939537911+18135696597948930n}$

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

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,}$

donde denota la función máximo común divisor . La secuencia de diferencias 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, 47, 3, 1, 5, 3, ... (secuencia A132199 en el 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 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 ]}${\displaystyle \gcd }$${\displaystyle a_{n+1}-a_{n}}$${\displaystyle \gcd(n+1,a_{n})}$

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

${\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 se pueden utilizar para producir una desigualdad polinómica generadora de números primos en 26 variables: ${\displaystyle \alpha _{0},\dots ,\alpha _{13}}$

${\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 a medida que las variables recorren los enteros no negativos. ${\displaystyle a,b,...,z}$

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 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 , 92 (1): 49– 52, doi : 10.1007/BF02866907( erratas )

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