Il gioco per computer online “Is this prime?” mette alla prova la conoscenza dei numeri primi di un giocatore e ha appena superato i 2.999.999 tentativi di stabilire un record da parte degli utenti.
di Siobahn Roberts
Il matematico greco Euclide ha dimostrato, intorno al 300 a.C., che esistono infiniti numeri primi, ma è stato il matematico britannico Christian Lawson-Perfect che, più recentemente, ha ideato il gioco per computer “Is this prime?“.
Risalente a cinque anni fa, il gioco ha superato i tre milioni di tentativi il 16 luglio o, più precisamente, ha raggiunto la cifra di 2.999.999, dopo che un post di “Hacker News” ha generato un’impennata di circa 100.000 tentativi.
Lo scopo del gioco è ordinare il maggior numero possibile di numeri in “primi” o “non primi” in 60 secondi (come originariamente descritto da Lawson-Perfect su “The Aperiodical”, un blog di matematica di cui è fondatore ed editore). Un numero primo è un numero intero con esattamente due divisori, 1 e se stesso.
“È molto semplice, ma estremamente difficile”, afferma Lawson-Perfect, che lavora nella divisione di e-learning della School of Mathematics and Statistics della Newcastle University. Lawson scrive software di valutazione elettronica (sistemi che valutano l’apprendimento) e ha creato il gioco nel suo tempo libero.
“Il sistema che realizzo è progettato per generare casualmente un quesito matematico e ricevere una risposta dallo studente, che contrassegna automaticamente e fornisce feedback”, afferma. “Si può pensare al gioco dei numeri primi come una sorta di valutazione. Lo ho usato infatti durante le sessioni di divulgazione nelle scuole.
Lawson ha reso il gioco leggermente più semplice con le scorciatoie da tastiera (i tasti y e n fanno clic sui corrispondenti pulsanti sì-no sullo schermo) per risparmiare tempo durante lo spostamento del mouse. (Per provare a giocare cliccare sul link)
Algoritmi di controllo della primalità
I numeri primi hanno un’utilità pratica nell’informatica, per esempio con i codici di correzione degli errori e la crittografia. Ma mentre la scomposizione in fattori primi è difficile (da qui il suo valore nella crittografia), il controllo della primalità è più “facile”. Il matematico tedesco Alexander Grothendieck, vincitore della Fields Medal, ha clamorosamente scambiato il 57 per numero primo (il “primo di Grothendieck”).
Quando Lawson-Perfect ha analizzato i dati del gioco, ha scoperto che vari numeri mostravano una tendenza a essere scambiati per primi. Quello più gettonato era il 51, seguito da 57, 87, 91, 119 e 133, la nemesi di Lawson-Perfect (esiste anche un pratico servizio di controllo della primalità).
L’algoritmo più minimalista per verificare la primitività di un numero è la divisione di prova: dividere il numero per ogni numero fino alla sua radice quadrata (il prodotto di due numeri maggiori della radice quadrata sarebbe maggiore del numero in questione).
Tuttavia, questo semplice metodo non è molto efficiente, e nemmeno altre tecniche escogitate nel corso dei secoli: come osservò il matematico tedesco Carl Friedrich Gauss nel 1801, “richiedono un lavoro intollerabile anche per il più infaticabile calcolatore”.
L’algoritmo che Lawson-Perfect ha codificato per il gioco è chiamato test di primalità di Miller-Rabin (che si basa su un metodo molto efficiente, ma non ferreo ,del XVII secolo, il “piccolo teorema di Fermat“). Il test di Miller-Rabin funziona sorprendentemente bene. Per quanto riguarda Lawson-Perfect, è “fondamentalmente magico” – “Non capisco davvero come funziona, anche se sono sicuro che potrei farlo se passassi il tempo a guardarlo più a fondo”, sostiene.
Poiché il test utilizza la casualità, produce un risultato probabilistico. Il che significa che a volte il test mente. “C’è la possibilità di scoprire un impostore, un numero composto che sta cercando di passare per primo”, afferma Carl Pomerance, matematico del Dartmouth College e coautore del libro Prime Numbers: A Computational Perspective. Tuttavia, le possibilità che un impostore scivoli attraverso l’intelligente meccanismo di controllo dell’algoritmo sono forse una su un trilione, quindi il test è “abbastanza sicuro”.
Ma per quanto riguarda gli algoritmi di controllo della primalità, il test di Miller-Rabin è “la punta dell’iceberg”, afferma Pomerance. In particolare, 19 anni fa, tre scienziati informatici – Manindra Agrawal, Neeraj Kayal e Nitin Saxena, tutti dell’Indian Institute of Technology, a Kanpur – hanno annunciato il test di primalità AKS (ancora una volta basato sul metodo di Fermat), che alla fine ha fornito un test per dimostrare inequivocabilmente che un numero è primo, senza randomizzazione e (almeno in teoria) con una velocità impressionante.
Ahimè, veloce in teoria non si traduce sempre in veloce nella vita reale, quindi il test AKS non è utile per scopi pratici.
Il record mondiale non ufficiale
Ma la praticità non è sempre il punto. Occasionalmente Lawson-Perfect riceve e-mail da persone desiderose di condividere i loro punteggi più alti nel gioco. Recentemente un giocatore ha riportato 60 numeri primi in 60 secondi, ma il record è più probabile che sia 127. (Lawson-Perfect non tiene traccia dei punteggi più alti; sa che ci sono alcuni imbroglioni, con tentativi assistiti dal computer che producono picchi nei dati).
Il punteggio di 127 è stato ottenuto da Ravi Fernando, uno studente laureato in matematica presso l’Università della California, a Berkeley, che ha pubblicato il risultato nel luglio del 2020. È ancora il suo record personale e, secondo lui, il “record mondiale non ufficiale”.
Dall’estate scorsa, Fernando non ha giocato molto con le impostazioni predefinite, ma ha provato con impostazioni personalizzate, selezionando numeri più grandi e consentendo limiti di tempo più lunghi: ha segnato 240 con un limite di cinque minuti. “Ha richiesto grande riflessione perché i numeri erano a quattro cifre alte e ho sempre memorizzato solo i numeri primi fino ai 3.000 bassi”, spiega.
Il suo campo di ricerca è la geometria algebrica, che coinvolge in una certa misura i numeri primi. Ma, conclude, “la mia ricerca ha più a che fare con il motivo per cui ho smesso di giocare rispetto al motivo per cui ho iniziato” (ha iniziato il suo dottorato nel 2014).
Immagine di: Ms Tech / Pixabay
(rp)
