Cribas

Ve¨ªamos la semana pasada que el matem¨¢tico chino Chen Jingrun demostr¨® el teorema que lleva su nombre utilizando la teor¨ªa de cribas, un poderoso m¨¦todo que se remonta, por lo menos, al siglo III a. C.

En efecto, la m¨¢s famosa de las cribas num¨¦ricas es la de Erat¨®stenes (276-194 a. EC.), un sencillo algoritmo (del tipo ¡°la cuenta de la vieja¡±) para hallar los primos menores que un determinado n¨²mero natural n. Se escriben los n¨²meros comprendidos entre 2 y n y se van tachando los que no son primos en pasos sucesivos: se empieza por el 2 y se tachan todos sus m¨²ltiplos (o sea, todos los pares); se vuelve al comienzo de la lista y el primer n¨²mero no tachado, el 3, es primo, y se procede a tachar todos sus m¨²ltiplos, y as¨ª sucesivamente. El proceso termina cuando el cuadrado del ¨²ltimo primo as¨ª encontrado es mayor que n.

Busquemos, por ejemplo, los primos menores que 20. Listamos los n¨²meros del 2 al 20 y marcamos los m¨²ltiplos de 2:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

El primer n¨²mero no marcado es el 3, as¨ª que se marcan sus m¨²ltiplos:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

El siguiente n¨²mero no marcado es el 5, y como su cuadrado es mayor que 20, el proceso ha terminado y los primos son los n¨²meros no marcados:

2 3 5 7 11 13 17 19

El proceso, un tanto engorroso si la lista de n¨²meros es larga, se puede simplificar (?de qu¨¦ manera?).

Como an¨¦cdota (y dato de inter¨¦s para programadores), la versi¨®n inform¨¢tica de la criba de Erat¨®stenes se convertir¨ªa en un m¨¦todo est¨¢ndar para comparar la eficacia de diferentes lenguajes de programaci¨®n.

M¨¢s a¨²n que por su criba, Erat¨®stenes es famoso por su c¨¢lculo, notablemente preciso, del di¨¢metro de la Tierra, as¨ª como por convertir la geograf¨ªa y la geodesia en disciplinas con entidad y m¨¦todos propios, introduciendo procedimientos y terminolog¨ªas que a¨²n se siguen utilizando. Pero ese es otro art¨ªculo.

Otras cribas

En la estela de Erat¨®stenes, otras cribas (demasiado avanzadas para tratarlas aqu¨ª, aunque su fundamento matem¨¢tico es relativamente simple), como la de Euler, la de Legendre, la de Brun, la de Selberg o el denominado ¡°cribado grande¡±, han permitido conseguir algunos ¨¦xitos parciales en la desesperante tarea de abordar la conjetura de Goldbach. Como el teorema de Bombieri-Friedlander-Iwaniec, que demuestra que hay infinitos n¨²meros primos de la forma a? + b?, siendo a y b n¨²meros enteros y positivos no necesariamente distintos (invito a mis sagaces lectoras/es a hacer la lista de los primeros primos de este tipo y sacar alguna conclusi¨®n). Y Chen Jingrun, que, como vimos, demostr¨® que todo n¨²mero par lo suficientemente grande es la suma de dos primos o de un primo y un semiprimo. A su vez demostr¨® que existen infinitos primos p tales que p+2 es primo o semiprimo, un importante paso hacia la demostraci¨®n de la conjetura de los n¨²meros primos gemelos, seg¨²n la cual hay infinitas parejas de ellos.

A mediados del siglo XIX, el matem¨¢tico franc¨¦s Alphonse de Polignac formul¨® una conjetura m¨¢s general seg¨²n la cual, para todo n¨²mero natural n, existen infinitos pares de primos cuya diferencia es 2n. En el caso de n = 1, tenemos la conjetura de los n¨²meros primos gemelos. ?Puedes hallar algunos pares de primos para n = 2, 3, 4¡­?

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aqu¨ª para recibir nuestra newsletter semanal.