Dado un número primo, ¿qué fórmula puedo usar para encontrar el siguiente?

Cuando uno hace matemáticas lo normal es pensar que todo puede definirse en términos rigurosamente formales de tal manera que toda pregunta siempre tiene una respuesta “blanco/negro”, “sí/no”, “verdadero/falso”, “sí, aquí tienes una fórmula/no, no existe ninguna”.

Desafortunadamente, las matemáticas son un área del conocimiento tan humana como cualquier otra, y a pesar de que la mayoría de los términos útiles tienen definiciones limpias, formales y rigurosas, también hay términos que no tienen una definición precisa y universalmente aceptada, y que dependen mucho de la subjetividad de quien los estudia.

En este caso, el término que tiene un elemento subjetivo es fórmula. ¿Y una “fórmula” qué es? Yo te puedo ofrecer fórmulas para calcular primos, pero nada me garantiza de antemano que tú vas a estar satisfecho con alguna de ellas. Bien podrías considerarlas “trampa” o que no son fórmulas en absoluto.

Con esa observación, permíteme adelantarte la respuesta: sí existen fórmulas que hacen exactamente lo que quieres, pero son de una complejidad computacional tan grande que en la práctica no sirven para nada.

Si yo te digo que existe una función EsPrimo(n)EsPrimo⁡(n) que vale 11 precisamente cuando nn es primo y 00 cuando no lo es, probablemente vas a sospechar de mí: ¿cómo haces para calcular EsPrimo(n)EsPrimo⁡(n)? ¿Eso no equivale directamente a aplicar la criba de Eratóstenes u otro método semejante? Y sí, desde luego, pero ¿le dirías lo mismo a alguien que usara la función seno o coseno o logaritmo dentro de una fórmula? Y al cabo, ¿sabe alguien calcular senos, cosenos o logaritmos, que no sea aproximándolos con métodos numéricos? ¿Me exigirías una fórmula para calcular logxlog⁡x dado xx?

Así que déjame por un momento usar EsPrimo(n)EsPrimo⁡(n), y te prometo que valdrá la pena. Esto es lo que voy a usar para construir la fórmula del “siguiente primo”, que es lo que me pides en tu pregunta.

Observa primero que 1−EsPrimo(n)1−EsPrimo⁡(n) vale 11 precisamente cuando nn no es primo, y de lo contrario vale 00. En consecuencia, si consideras los kk números n+1,n+2,…,n+k,n+1,n+2,…,n+k, entonces la expresión

(1−EsPrimo(n+1))(1−EsPrimo(n+2))⋯(1−EsPrimo(n+k))(1−EsPrimo⁡(n+1))(1−EsPrimo⁡(n+2))⋯(1−EsPrimo⁡(n+k))

va a ser un producto de unos si todos los números n+1,…,n+kn+1,…,n+k son compuestos, y en consecuencia su valor será 11. En cambio, si hay algún primo colado en esos kk números, todo el producto se hará cero. Démosle, pues, un nombre a esta expresión: ¿te parece F(n,k)F(n,k)?

Tenemos, pues,

F(n,k)={10si n+1,…,n+k son todos compuestos,si alguno es primo.F(n,k)={1si n+1,…,n+k son todos compuestos,0si alguno es primo.

Y con eso ya puedo hacer el siguiente truco de magia: si p(n)p(n) es el siguiente primo mayor que nn, entonces

p(n)=n+1+∑k=1nF(n,k).p(n)=n+1+∑k=1nF(n,k).

Y ésa es la fórmula que estabas buscando.

Espera, ¿qué? ¿Y eso cómo funciona?

Resulta que F(n,k)F(n,k) vale 11 mientras no alcancemos un primo, y tan pronto como llegamos a un primo el resto de los sumandos valen cero, y dejamos de contar. El postulado de Bertrand garantiza que solamente tenemos que contar hasta 2n2n, ya que siempre hay un primo entre nn y 2n2n. Por eso la suma llega hasta k=nk=n.

Así pues, no es necesario que el propio nn sea primo, pero es garantizado que p(n)p(n) va a ser el siguiente primo mayor que nn.

Lo más probable es que pienses que esta fórmula es muy tramposa, así que en esta última sección la voy a escribir de una forma un poquito más explícita.

Resulta que

EsPrimo(n)=⌊cos2((n−1)!+1nπ)⌋.EsPrimo⁡(n)=⌊cos2⁡((n−1)!+1nπ)⌋.

La razón por la cual tenemos esta intrigante fórmula para la función EsPrimoEsPrimo es el teorema de Wilson: un entero n≥2n≥2 es primo si y sólo si (n−1)!+1(n−1)!+1 es múltiplo de nn. Cuando eso ocurre, la expresión entre paréntesis es un múltiplo entero de ππ, y su coseno al cuadrado será 11. De lo contrario, la expresión entre paréntesis no será un múltiplo entero de ππ y su coseno al cuadrado será algún número no negativo menor que 11, cuya parte entera será entonces cero.

Ahora ya estamos listos para dar la fórmula explícita del siguiente primo mayor que nn:

p(n)=n+1+∑k=1n∏j=1k(1−⌊cos2((n+j−1)!+1n+jπ)⌋).p(n)=n+1+∑k=1n∏j=1k(1−⌊cos2⁡((n+j−1)!+1n+jπ)⌋).

Como ves, computacionalmente esta fórmula no sirve para nada. Algo así va a pasar con cualquier fórmula que haga lo que tú pides. Para encontrar primos hay algoritmos computacionalmente muy eficientes, ninguno de los cuales puede escribirse de manera práctica como una fórmula matemática. Es una pena, pero no deja de llamar la atención que con unos cuantos trucos lógico-aritméticos como los de arriba uno sea capaz de escribir EsPrimo(n)EsPrimo⁡(n) y p(n)p(n) como fórmulas explícitas.