Una fórmula para generar números primos

Los números primos son escurridizos; fáciles de definir y difíciles de encontrar. Entender cómo se distribuyen, qué patrones siguen o cómo distinguirlos del resto de números son problemas que han traído de cabeza a los matemáticos durante milenios. ¡Y todavía estamos lejos de una respuesta satisfactoria!

Dicen que encontrar una fórmula eficiente capaz de generar todos los números primos sería el mayor éxito de la teoría de números, pues resolveríamos de un plumazo todas las incógnitas que los envuelven. Aunque no todo sería jolgorio: en los primos hemos basado la seguridad de Internet, y conseguir una fórmula de tal calibre sería un paso hacia la destrucción -momentánea- de las telecomunicaciones actuales.

¿Cuál es el problema?

Un número primo es aquel que solo se puede dividir por uno o por sí mismo. El número ocho, por ejemplo, no es primo porque se puede por dos. El número siete sí que es primo.

Esta definición permite crear métodos para encontrar números primos. El número primo más pequeño es el dos. Si colocamos todos los números naturales en fila, podemos señalar el dos como primo y tachar todos los números de la lista que se puedan dividir por dos (el 4, el 6, el 8, …), ya que estos no serán primos.

\boxed2  ~~~ 3 ~~~ \cancel 4 ~~~ 5  ~~~ \cancel 6 ~~~ 7 ~~~ \cancel 8 ~~~ 9  ~~~ \cancel{10} ~~~ 11 ~~~ \cancel{12} ~~~ 13 ~~~ \cancel{14} ~~~ 15 ...

Al terminar, el primer número sin tachar de la lista es el tres. El tres debe ser primo, pues no se puede dividir por ningún número más pequeño, salvo el uno. Recuadramos el tres como primo y tachamos todos los números que se puedan dividir por tres (el 6, el 9, el 12, …), ya que no serán primos.

\boxed2  ~~~ \boxed3 ~~~ \cancel 4 ~~~ 5  ~~~ \cancel 6 ~~~ 7 ~~~ \cancel 8 ~~~ \cancel9  ~~~ \cancel{10} ~~~ 11 ~~~ \cancel{12} ~~~ 13 ~~~ \cancel{14} ~~~ \cancel{15} ...

Al terminar, el primer número sin tachar de la lista es el cinco, que debe ser primo porque no se puede dividir por ningún número más pequeño, salvo el uno. Si repetimos el proceso —tachar los múltiplos y comenzar de nuevo con el primer número que quede sin tachar—, obtendremos una lista con todos los números primos que existen.

\boxed2  ~~~ \boxed3 ~~~ \cancel 4 ~~~ \boxed5  ~~~ \cancel 6 ~~~ \boxed7 ~~~ \cancel 8 ~~~ \cancel9  ~~~ \cancel{10} ~~~ \boxed{11} ~~~ \cancel{12} ~~~ \boxed{13} ~~~ \cancel{14} ~~~ \cancel{15} ...

Este procedimiento se denomina criba de Eratóstenes. Produce una lista de números primos con una receta fácil y repetitiva. Pero presenta varios problemas: si queremos encontrar números primos muy grandes, este algoritmo requerirá mucho tiempo de cálculo. Además, no es una fórmula en la que podamos sustituir un número y conseguir un resultado, sino un proceso con varios pasos.

Surge un problema natural con los números primos: ¿existe alguna fórmula sencilla que genere números primos?

Fórmulas sencillas

Todos los primos, solo los primos

Podemos matizar muchos detalles de la fórmula generaprimos que buscamos. El primero es básico, pero importante: no solo nos interesa que la fórmula genere todos los primos, sino que genere solo números primos. Es decir, la fórmula

f(n)=n+2

produce todos los números primos porque, en esencia, produce todos los números naturales mayores o iguales que 2 según vamos dándole valores a n\in \mathbb{N}. Está claro que no tiene mucho interés, porque no genera solo números primos, aunque sí los genere todos.

Fórmulas sin fórmulas

Encontrar una fórmula que genere todos números primos, y solo números primos, es más fácil de lo que parece. Por ejemplo, podemos inventar una fórmula f(n) que devuelve el nº número de la criba de Eratóstenes. En ese caso, f(4)=7, pues siete es el número que aparece en cuarta posición en la criba de Eratóstenes, como hemos visto en la sección anterior.

Matemáticamente es una función perfectamente válida, pero tiene un problema: ¿cómo se calcula el resultado que produce esa fórmula? Cuando la gente piensa en una fórmula, piensa en una expresión que tiene sumas, restas, multiplicaciones, divisiones y otras operaciones reconocibles. En este caso, ¿qué expresión tiene la función que acabamos de inventar? Sí, hay que buscar el número primo en una lista, pero ¿cómo se traduce eso a las operaciones habituales? ¡No está muy claro!

f(n) =~~  ?

Lo que quiero remarcar es que una fórmula generaprimos útil debe tener una expresión similar a la de los polinomios: algo formado por sumas, restas, multiplicaciones y potencias. No queremos una fórmula que se pueda describir con palabras. ¡Queremos una fórmula que nos diga cómo se hacen los cálculos!

La fórmula de marca blanca

Puede que la expresión más sencilla y famosa en este asunto sea el polinomio cuadrático de Euler, encontrado en 1772:

f(n)=n^2+n+41 .

Si sustituyes el valor de n por cualquier número natural del 0 al 39, el resultado obtenido es un número primo. ¿No es genial?

Por desgracia, la fórmula de Euler no tiene mucho más que ofrecer. En primer lugar, porque al probar con n=40 devuelve un número compuesto: no solo genera números primos. Y, después, porque no produce todos los números primos: solo algunos, y siempre mayores de 41. Es imposible, por ejemplo, que esta fórmula genere el 2 o el 11.

Durante siglos los matemáticos han encontrado fórmulas parecidas a la de Euler. Todas tienen los mismos problemas: no generan todos los números primos, y no generan solo números primos. Y como todos los intentos por encontrar la fórmula eran infructuosos, los matemáticos se convencieron de que la expresión generaprimos que buscaban no existía. Que era un sueño inalcanzable. Pero hace cincuenta años, las tornas cambiaron.

Una fórmula completa

Supongo que puedo soltar el bombazo ya. Sí, existen varias fórmulas polinómicas que generan todos los números primos, y solo los números primos. En particular, la propuesta por Jones et al. en 1976 es el ejemplo más conocido:

Este polinomio de grado 25 produce todos los números primos que existen. El aspecto es infernal, pero no es difícil de utilizar: elige un valor natural para cada una de sus 26 variables (por ejemplo, a=1, b=2, …, z=26) y sustitúyelo en el polinomio. Si el resultado es un número positivo, entonces será primo. Si es negativo, descártalo y prueba otra vez. Según vas dándole valores a todas las variables, irás obteniendo todos los números primos que existen. Sin dejarse ninguno. Sin excepciones.

¿De dónde sale esta fórmula? En la década de los sesenta se demostró un teorema que reza que cualquier conjunto definido de forma recursivamente enumerable, como los números primos, se puede describir de forma polinomial. En cristiano: el teorema demuestra que existe una fórmula polinomial capaz de generar todos los números primos. Esto devolvió la ilusión al mundo de los números primos. La fórmula existía. Solo había que esperar a que alguien la encontrara.

Y no solo se encontró una fórmula: ¡había muchas! La que he escrito en la pizarra anterior es una de las tantas que existen. Con las herramientas adecuadas puedes deducir un amplio abanico de polinomios, de distintos grados y distinto número de variables, que produzcan únicamente números primos, sin dejarse ninguno fuera, como el de la imagen de arriba. Por desgracia, todos estos polinomios tienen truco y no son tan bonitos como los pintan.

El gozo en un pozo

Hay un detalle que chirría al describir el polinomio generaprimos de arriba. Eso de que solo genera números primos no es cierto. Ya lo hemos dicho: si al sustituir las 26 variables el resultado es negativo, entonces hay que descartarlo y no nos aporta información. Hay que probar con otros valores. La pregunta es: ¿cómo de frecuentes son los resultados negativos?

La estructura del polinomio genera-primos de arriba se puede simplificar bastante. Si te fijas, tiene dos partes principales. La primera es el factor (k+2). La segunda es un 1 al que se le restan muchos términos al cuadrado.

p(a,..., z) = (k+2)\cdot(1-\alpha_1^2-\alpha_2^2 -\cdots-\alpha_{14}^2)

El valor de los \alpha_i lo puedes encontrar mirando el polinomio de la imagen. Por dar un ejemplo, los dos primeros serían

\begin{array} {lcl} \alpha_1 &= & wz + h +j -q \\ \alpha_2  &= & (gk + 2g + k +1)(h+j) + h -z\end{array}

Los números primos aparecen cuando el polinomio devuelve un resultado positivo. ¿Cómo de frecuentes son los resultados positivos? De risa, la verdad. Solo hay una manera de hacer que el segundo factor sea positivo: conseguir que todos los \alpha_i se hagan cero. Si alguno de ellos no es cero, entonces el resultado final no será positivo y el polinomio no producirá un número primo.

Si quieres hacer que todos los \alpha_i se hagan cero de manera expresa, tendrás que resolver un sistema de 14 ecuaciones no lineales, con 26 incógnitas que solo toman valores enteros. En otras palabras, una locura.

\left\lbrace \begin{array} {lcl} 
\alpha_1 & = & wz + h +j -q &=& 0\\ 
\alpha_2 & = & (gk + 2g + k +1)(h+j) + h -z  &=&0\\
&\cdots \\
\alpha_{14} & = & z + pl(a-p) + t(2ap-p^2-1)-pm &=& 0
\end{array}\right.

Si quieres asegurarte de obtener un resultado positivo en este océano de resultados negativos, tendrás que hacer un esfuerzo sobrehumano y resolver un sistema de catorce ecuaciones diofánticas. No es un método eficiente para encontrar números primos.

Por eso, aunque la fórmula es un éxito de la teoría de números, no tiene utilidad práctica. Es como una ruleta, no permite saber de antemano si el resultado va a ser positivo (y primo) o negativo (e inútil). ¡Y hay muchas más posibilidades de que salga negativo! Aunque a nivel teórico sea muy impactante, no es una fórmula práctica para encontrar todos los números primos.

¿Y entonces qué?

¿Existen las fórmulas que generan primos? ¡Sí, hay muchas! ¿Existen fórmulas que generan primos y tienen forma de polinomio? ¡Sí, muchas también! ¿Entonces por qué los números primos siguen siendo un tema de investigación matemática tan interesante y activo? Por un detalle que no hemos comentado todavía: por la eficiencia.

Hoy en día no conocemos ningún método eficiente para calcular números primos. Al menos, que se haya hecho público. Tenemos muchas fórmulas distintas. Algunas son más sencillas, algunas son más complicadas. Ninguna consigue encontrar todos los números primos en un tiempo razonable. Todas requieren muchos cálculos y muchos recursos para obtener un resultado satisfactorio. En otras palabras, ninguna de las fórmulas que conocemos es eficiente.

¿Existe una fórmula eficiente que genere todos los números primos, y solo los números primos? ¡No lo sabemos! No se ha demostrado que sea imposible, pero nadie ha encontrado la respuesta. Por tanto, podemos seguir confiando en los números primos para mantener la seguridad de las comunicaciones por Internet, y para seguir enamorando a los matemáticos soñadores con un problema profundo y misterioso.