Fórmula de los números primos

En matemáticas, la fórmula de los números primos es una fórmula que genera los números primos, exactamente y sin excepción alguna. Otro gran acuerdo a esto es qué se considera como una "fórmula" y que no. No existe ninguna fórmula polinómica para obtener todos los números primos. Tampoco existe alguna fórmula polinómica no constante que sólo obtenga valores primos. La mayoría de la gente puede objetar que el término "fórmula" se restringe solamente a los polinomios. ¿Podría uno usar sumatorias, factoriales y la función piso? Si así fuera, de hecho, sí existen fórmulas de los números primos. Una interpretación razonable de la palabra "fórmula" es "una máquina de Turing que se detiene bajo todas las entradas". Bajo esta interpretación ciertamente existen máquinas de Turing que se detienen las cuales computan el enésimo número primo. Aun así, nadie sabe cómo calcular el enésimo número primo en tiempo polinómico. Dicho de otra forma, no se conoce alguna fórmula fácilmente computable.

Funciones polinómicas

Se sabe que no existe una función polinómica no constante $P(n)\,\!$ que evalúe números primos para todos los enteros n. La comprobación a esto es simple: Supongamos que dicho polinomio existe. Entonces $P(1)\,\!$ evaluaría al primo p, entonces $P(1)\equiv 0{\pmod {p}}$ . Para cualquier k, $P(1+kp)\equiv 0{\pmod {p}}$ , así que $P(1+kp)\,\!$ no puede ser primo (si lo fuera, fuera divisible por p) a menos que fuera el mismo p. La única forma en que $P(1+kp)=P(1))\,\!$ para toda k es si la función polinómica es constante.

Si aplicamos más la teoría de los números algebraicos, se puede mostrar un resultado aún mayor: no existe una función polinómica no constante P(n) que evalúe a un número primo para casi todos los enteros n.

El polinomio cuadrático

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

devuelve números primos para todos los enteros no negativos menores que 40. Los números primos para $n=0,1,2,3...\,\!$ son $41,43,47,53...\,\!$. Las diferencias entre los términos son $2,4,6,8,10...\,\!$. Para $n=40\,\!$, se produce un número cuadrado, $1681\,\!$, el cual es igual a $41\cdot 41$, el menor número compuesto para esta fórmula. De hecho si 41 divide a n, también divide a $P(n)\,\!$. El fenómeno se relaciona con la espiral de Ulam, la cual también es implícitamente cuadrática.

Basándonos en el teorema de Dirichlets sobre las progresiones aritméticas se sabe que funciones lineales $f(x)=ax+b\,\!$ producen infinitos números primos siempre y cuando a c ' y 'b sean primos relativos (aunque tal función no asumirá valores primos para cualquier x).

No se conoce si existe un polinomio invariable de al menos grado mayor que 2 que genere un número infinito de valores que son primos.

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

Un conjunto de ecuaciones diofánticas en 26 variables puede ser usada para obtener números primos. Jones demostró que dado un número $k+2\,\!$ éste es primo si y solo si el siguiente sistema de 14 ecuaciones diofánticas tiene una solución en los números naturales:

$0=<math>0=(gk+2g+k+1)(h+j)+h-z\,\!$

$0=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}\,\!$

$0=2n+p+q+z-e\,\!$

$0=e^{3}(e+2)(a+1)^{2}+1-o^{2}\,\!$

$0=(a^{2}-1)y^{2}+1-x^{2}\,\!$

$0=16r^{2}y^{4}(a^{2}-1)+1-u^{2}\,\!$

$0=n+l+v-y\,\!$

$0=(a^{2}-1)l^{2}+1-m^{2}\,\!$

$0=ai+k+1-l-i\,\!$

$0=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}\,\!$

$0=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m\,\!$

$0=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x\,\!$

$0=z+pl(a-p)+t(2ap-p^{2}-1)-pm\,\!$

Esto puede ser usado para producir un polinomio que genere números primos. Denotemos los lados derechos de las ecuaciones de arriba por $\alpha _{1},\alpha _{2},\cdots ,\alpha _{14}$. Entonces:

$(k+2)(1-{\alpha _{1}}^{2}-{\alpha _{2}}^{2}-\cdots -{\alpha _{14}}^{2})$

es un polinomio de 26 variables, y el conjunto de los números primos es idéntico al conjunto de los valores positivos tomados por este polinomio con los valores $a,b,\cdots ,z$ del rango sobre los enteros no negativos.

Un teorema general de Matiyasevich dice que si un conjunto se define como un conjunto de ecuaciones diofánticas, también puede ser definido como un sistema de ecuaciones diofánticas con sólo 9 variables. Por lo tanto, existe un polinomio que genera números primos como el anterior de tan sólo 10 variables. Sin embargo, el grado de dicho polinomio es muy grande (del orden de $10^{45}\,\!$). Visto de otra manera, también podemos transformar dicho polinomio a grado 4, pero con 58 variables.