El Teorema del Número Primo: buscando primos entre los naturales

En algunas de las secciones de estas páginas ya he hablado de números primos. El Teorema de Fermat, es uno de esos teoremas sobre ecuaciones y números primos que después del esfuerzo de muchos ha quedado demostrado, aunque ha sido el matemático británico Wiles el que ha tenido el privilegio de ser el primero en ascender a la cumbre. También hemos hablado sobre la sucesión de los números primos: la demostración de que es una sucesión infinita, es muy antigua, y no demasiado difícil de entender.

Encontrar regularidades en la sucesión de los números primos se ha convertido en uno de los problemas más intrincados de la matemática actual. La dificultad de manejo de números primos grandes ha permitido el diseño de sistemas criptográficos que permiten el intercambio de información de manera segura en Internet. En teoría, saber si un número es primo o no, es sencillo: basta averiguar si es divisible por algún número más pequeño que él mismo. Pero si el número es muy grande esta tarea se convierte en muy difícil, incluso con ordenadores muy potentes. Este problema es NP-duro, lo que significa que el tiempo que tarda un algoritmo en resolver el problema, crece exponencialmente con el tamaño del problema.

Los números primos se distribuyen de manera irregular entre los enteros y parece que no es fácil predecir dónde van a aparecer. Veamos algunos ejemplos: resulta evidente que un número primo tiene que ser impar, excepto el 2, y por lo tanto la diferencia entre dos primos consecutivos ha de ser un número par, pero aquí se acaban las facilidades. Al buscar los números primos entre 9999900 y 10000000 nos encontramos los siguientes:

9999901
9999907
9999929
9999931 9999937 9999943
9999971 9999973 9999991

Pero en cambio entre 10000000 y 10000100 sólo hay dos primos: el 10000019 y el 10000079.

Candidatos a primos

Se pueden encontrar series de números naturales arbitrariamente largas entre dos primos consecutivos, y es posible generar números primos muy grandes. Pero no hay una fórmula (que yo sepa) capaz de generar sólo, números primos. Algunas fórmulas son capaces de generar buenos candidatos a número primo.

El demostración de Euclides de la infinitud de los números primos sugiere una manera de conseguirlo: vamos a generar, por ejemplo, los números primos menores que 100, los multiplicamos y sumamos 1. Para generar dicha lista vamos a usar la criba de Erastótenes, que consiste en lo siguiente:

    1. Supongamos la lista de números enteros del 1 al 100. En un primer paso eliminamos los múltiplos de 2, es decir todos los pares, excepto el 2 (celdas de fondo rojo)
    2. Después elegimos el siguiente primo: en este caso el 3, y eliminamos todos sus múltiplos, que no hayan sido ya eliminados en el paso anterior (celdas de fondo azul)
    3. En un tercer paso eliminamos todos los múltiplos de 5 (fondo verde).
    4. En este caso el trabajo termina con el 7, ya que el 8, 9 y 10 ya han sido eliminados y el 11 es mayor que la raíz de 100 (fondo negro)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

En otra sección de esta Web (aquí) hemos visto que N = 1*2*3*5* ...* pm + 1, no siempre es un número primo siendo 1, 2, 3, 5, ..., pm la lista de todos los números primos hasta el primo pm. Pero desde luego es un buen candidato, Este número, si tiene divisores, serán mayores que 97 (es decir, mayores o iguales que 101, primo siguiente a 97)

2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97 +1 =

= 2305567963945518424753102147331756071

Primos de Mersenne

Los números primos más grandes conocidos se obtienen mediante la fórmula Mn = 2n-1, que no siempre genera primos, pero que genera muy buenos candidatos. En concreto para n = 1, 2, 3, 4, 5, 6 y 7, los números de Mersenne, con primos. Pero para n = 8, la racha se trunca. Cuando n es primo, en muchos casos Mn es primo. Por ejemplo, para n = 17, se tiene que M17 = 131071, que es primo. ¿Porqué es más sencillo estudiar si Mn es primo? La definición de estos números permite saber que el n-ésimo número de Mersenne es una cadena de n unos cuando se escribe en binario (base 2). Por ejemplo, M7 = 27 - 1 = 127 = 1111111 en base 2 es un número de Mersenne. Esta propiedad permite implementar cálculos con números de Mersenne en los computadores de manera más eficiente. No todos los primos son primos de Mersenne, pero como éstos se pueden implementar fácilmente en un programa de ordenador los 8 mayores primos conocidos son primos de Mersenne.

¿Orden?

Encontrar orden en este caos de números primos, no parece sencillo: algo se consigue, como vamos a ver, al considerar los primos en su conjunto, y no de forma individual. Para empezar, vamos a situarlos en espiral, y marcamos los primos en azul. Aparecen algunas regularidades no demasiado significativas, pero se observa que los primos tienden a escasear en la medida en que los números se hacen cada vez mayores.

En este cuadro se observan muy a menudo parejas de números primos consecutivos (ambos impares y con un par en medio): se les llama números primos gemelos, y por ejemplo pueden ser números como éstos 11-13, 1091-1093, 3257-3259, etc. ... Se supone que hay infinitas parejas de este tipo, pero hasta hoy nadie ha conseguido demostrarlo. Esta conjetura, llamada de Goldbach (hay otra conjetura con el mismo nombre, endemoniamente difícil), es uno de los grandes teoremas de la teoría de números pendiente de demostración (o refutación). En Teoría de números hay muchos teoremas pendientes de demostración.

Aquí puedes encontrar algunos de esos teoremas: ver

Dibujando la escasez de primos

La abundancia de primos hasta cierto valor n, tiende a disminuir en la medida en que n aumenta. El gráfico anterior está hecho a mano, con lo que no he podido llegar muy lejos en la representación. Pero he hecho un programa, que representa los primos en espiral. La idea es la siguiente: al ir dibujando puntos en espiral a partir del centro de la pantalla, y asignándole a cada punto un número natural, si el número no es primo, lo dibujamos en blando. Si es primo, en negro. Se obtiene entonces un gráfico como este:

Puede observarse que los puntos negros tienden a ser más escasos, en la medida en que nos alejamos del centro. Además el ordenador va calculando los primos hasta cada n. Se observa que hasta el número 1955769 hay 145905, lo que supone una densidad (aprox) de 7.46 primos cada 100 enteros. La representación de la densidad de primos, hasta cada número n (en la gráfica n= 100000), da la siguiente gráfica:

La línea azul corresponde al 10%. En los 100 primeros naturales, la densidad es muy alta: 25%. A partir a ahí, va disminuyendo, aunque muy lentamente. Si en la Tabla 1, multiplicas la tercera columna por 100, obtendrás la densidad en %, de números primos hasta cada n de la tabla.

Analizando la escasez de primos

Se ha podido estimar que en un intervalo [1, n] la distancia media entre cada par de primos gemelos es aproximadamente igual a (log n)2, es decir que las parejas de números primos son cada vez más escasas, como lo son los primos al tomar valores de n cada vez mayores: vamos a demostrar esta última afirmación. Para ello vamos a ver que los primos consecutivos pueden estar tan separados como se quiera. Observa la siguiente sucesión de números

a1 = n!+2
a2 = n!+3
a3 = n!+4
...
an-1 = n!+n

Esta sucesión de n-1 números, está formada por números consecutivos, no primos.. Si le damos a n el valor 100000, nos damos cuenta que tenemos una sucesión de 99999 números no primos y consecutivos.

Estas propiedades nos indican que los primos no están colocados al azar, pero los intentos de saber dónde se encuentran han fracasado. Vamos a explicar ahora qué dice el Teorema del número primo, que como veremos nos da alguna idea de cómo se distribuyen los números primos a lo largo de los números naturales. Consideremos la función p(n) = "número de primos menores o igual a n". Esta función mide la distribución de los primos a lo largo de los números naturales. La cantidad relativa de números primos que hay hasta n, se puede obtener por el cociente p(n)/n, y como es lógico esperar (según lo que hemos dicho), dicha cantidad debe tender a disminuir. Una tabla de valores para esta función, es la siguiente:

n
p(n)
p(n)/n
10
4
0,400000000
100
25
0,250000000
1000
168
0,168000000
10000
1229
0,122900000
100000
9592
0,095920000
1000000
78498
0,078498000
10000000
664579
0,066457900
100000000
5761455
0,057614550
1000000000
50847534
0,050847534

Tabla 1

Cuando se invierte la última columna se obtiene entonces una tabla como la siguiente:

n
p(n)
p(n)/n
n/p(n)
10
4
0,400000000
2,5
100
25
0,250000000
4,0
1000
168
0,168000000
6,0
10000
1229
0,122900000
8,1
100000
9592
0,095920000
10,4
1000000
78498
0,078498000
12,7
10000000
664579
0,066457900
15,0
100000000
5761455
0,057614550
17,4
1000000000
50847534
0,050847534
19,7

Tabla 2

Entonces se observa que al pasar de una potencia de 10 a la siguiente la diferencia es aproximadamente 2,3. Y a partir de aquí se puede conjeturar que p(n) se puede aproximar mediante el cociente n /( ln n), o equivalentemente que

Esta conjetura resulta ser cierta, y recibe el nombre de Teorema del Número primo. Aunque esta aproximación es sencilla, no es demasiado buena. Una de las mejores es la siguiente

siendo x(z) la función z de Riemann. La tabla siguiente da los valores de p(n) y de R(n), y permite comparar ambas funciones, que como puedes observar es sólo un poco mejor que la anterior.

n
p(n)
R(n)
100 000 000
5761455
5761552
200 000 000
11078937
11079090
300 000 000
16252325
16252355
400 000 000
21336326
21336185
500 000 000
26355867
26355517
600 000 000
31324703
31324622
700 000 000
36252931
36252719
800 000 000
41146179
41146248
900 000 000
46009215
46009949