Ci sono voluti sei anni e un nuovo algoritmo che sfrutta le GPU, ma lunedì 21 ottobre 2024 il progetto GIMPS ha annunciato che 2^136279841−1 è un numero primo, il 52.mo di Mersenne. Ok, potrebbe essercene qualcun altro, perché non tutti gli esponenti inferiori sono stati testati; ma la cosa è abbastanza improbabile.
I numeri primi di Mersenne si chiamano così perché l’abate Marin Mersenne aveva stilato una lista – non molto precisa, a dire il vero – di quali numeri della forma 2^p−1 sono primi. Perché tanto interesse da parte di Mersenne? Perché se 2^p−1 è primo allora 2^p−1(2^p−1) è un numero perfetto. (Eulero dimostrò poi che tutti i numeri perfetti pari sono di questa forma; nessuno sa se esista un numero perfetto dispari, ma non credo che siano molti i matematici che scommetterebbero sulla sua esistenza). E perché c’è tanto interesse in questi decenni? Perché esiste un algoritmo “relativamente” rapido (di Lucas-Lehmer, dal nome degli scopritori) per verificare se un numero di questo formato è primo. Relativamente rispetto a un numero generico, ovvio: però resta il fatto che se dobbiamo cercare numeri primi grandi tanto vale provare con questi.
E in effetti il GIMPS (Great Internet Mersenne Prime Search, il sito citato all’inizio del post) fa proprio quello. Come dicevo, il vecchio programma Prime95 che era stato quello usato finora per trovare i primi di Mersenne è stato spodestato da un nuovo programma nato per sfruttare le GPU in modo diverso dal fare una ricerca con ChatGPT. Lo scopritore, Luke Durant, è un trentaseienne che ha lavorato in NVIDIA (ma va?) e ha cominciato la sua ricerca solo da un anno, con un cluster di migliaia di GPU sparse su 17 nazioni. Naturalmente la primalità del numero trovato da Durant è stata verificata in modo indipendente da vari programmi diversi tra loro, fatti girare su architetture hardware e tipi di CPU diversa: in questi casi è sempre meglio essere molto attenti a evitare errori invisibili.
Si troveranno altri primi di Mersenne? Chi lo può sapere. Io tra l’altro faccio parte della minoranza convinta che essi siano finiti, anche se non ho nessuna idea di quanti ce ne possano essere…

Un’ultima curiosità: in esadecimale il numero si scrive con un 1 seguito da 34069960 F. Chiaramente tutti i primi di Mersenne sono della forma xFFF…FFF, dove x può valere 1, 3, 7 oppure F.

Mercoledì avevo raccontato di come Ron Graham avesse dimostrato che tutti i numeri maggiori di 77 erano strettamente egizi, cioè possono essere scritti come somma di numeri tutti distinti i cui inversi hanno somma 1. Come l’ha dimostrato? Basta leggere il suo papero, no? Riporto qua il suo ragionamento, che parte dal fatto che D. H. Lehmer aveva dimostrato che 77 non era strettamente egizio.

Graham ha calcolato una tabellona contenente una partizione per ciascun numero da 78 a 166, e ciascun numero dispari da 167 a 333. L’inizio di questa tabella è mostrato in figura. Ma perché proprio questi numeri? Perché gli servivano per costruire tutti gli altri. Per la precisione, chiaramente $\tfrac{1}{2}+\tfrac{1}{2} = 1$. Ma se allora abbiamo una partizione con $1 = \tfrac{1}{d_1} + \tfrac{1}{d_2} + \cdots + \tfrac{1}{d_k}$ e $\sum_1^k d_i = n$, possiamo costruirne una del tipo $1 = \tfrac{1}{2} + \tfrac{1}{2d_1} + \tfrac{1}{2d_2} + \cdots + \tfrac{1}{2d_k}$; tutti i termini sono distinti, perché nessun $d_i$ può essere 1, e la somma dei denominatori è 2$n$ + 2. Questo significa che prendendo i numeri da 78 a 166 nella tabella (l’articolo ha un refuso, tra l’altro) e applicando questo trucco otteniamo tutti i numeri pari da 168 a 334. Quindi sappiamo che tutti i numeri da 78 a 334 sono strettamente egizi. A questo punto Graham, da buon prestigiatore, tira fuori dal cappello un’altra somma che dà $\tfrac{1}{2}$, cioè $\tfrac{1}{3} + \tfrac{1}{7} + \tfrac{1}{78} + \tfrac{1}{91}$. Notate che tutti i denominatori sono dispari tranne il 78, e quindi raddoppiare i denominatori di un numero strettamente egizio non può creare doppioni… E per quanto riguarda il 78, “casualmente” non ci sono denominatori 39 nella tabella e quindi non può essere generato. In questo caso abbiamo che la nuova somma dei denominatori è 2$n$ + 179. Usando entrambe queste formule possiamo ora estendere la nostra tabella da 2·78 + 179 a 2·334 + 2, cioè da 335 a 670; e anche qui continuiamo a non avere denominatori 39 che ci rovinerebbero il gioco. Da qui possiamo estenderla a 1340 (raddoppiando tutti i numeri fino a 670 e notando che i numeri fino a 570 con la seconda formula ci fanno arrivare a 1339) e così via. Quod erat demonstrandum :-)

La dimostrazione non è bella, concordo con voi; la tabella è troppo grande per essere accettabile esteticamente. Ma meglio una tabella e un po’ di teoria che nessun teorema. Tra l’altro, costruire la tabella oggi non sarebbe chissà quale problema, e anzi potremmo facilmente calcolare tutte le possibili partizioni per quei numeri in pochi secondi; ma ricordo che l’articolo è stato pubblicato nel 1963, e anche se Graham lavorava ai Bell Labs che probabilmente aveva computer all’avanguardia non è che ci fosse così tanta potenza di calcolo. Immagino che per parecchi numeri abbia usato la prima delle uguaglianze qui mostrate, e poi abbia usato alcuni trucchi partendo dalle partizioni “piccole”; ma comunque deve essere stato un lavoraccio. Ma ancora peggio deve essere stata la fatica di Lehmer per dimostrare che 77 non era strettamente egizio, visto che in questo caso non si possono trovare controesempi… di quello sì che mi piacerebbe vedere la dimostrazione!