Il giallo (presunto?) dei numeri primi

Premetto che ho messo la discussione sotto "informatica" poiché non esisteva una classificazione più adatta. Prego evt. Redazione di crearne una sotto "scienze e tecnologia".

Il 12 settembre ho visto [strike] questo curioso servizio de "Le Iene" [/strike] questo curioso servizio de "Le Iene" che parlava di un giovanissimo (13 enne) ragazzo calabrese, tale Rubens Alessio Martino che, a suo dire, avrebbe scoperto un algoritmo per scoprire la successione di tutti i numeri primi, ovvero quei numeri che possono essere divisi solo per 1 e per se stessi. I primi della lista sono 1, 3, 5, 7, ecc.
Forse ai più, questa scoperta non dirà molto, ma il problema dei numeri primi è considerato uno tra i più difficili della matematica. Da secoli ci si domanda se esista o meno un algoritmo (o metodo) in grado di prevedere la successione di questi numeri.
Essendo così difficili da scoprire, negli ultimi decenni sono stati sviluppati degli algoritmi di crittografia basati proprio sui numeri primi. Buona parte della sicurezza informatica di banche e grandi aziende (forse anche governative) si basa su questi algoritmi.
Finora, chi voleva forzare una di queste cifrature aveva bisogno di supercomputer con enorme potenza di calcolo.
Se qualcuno scoprisse davvero una scorciatoia per trovare questi numeri, anzitutto farebbe una grandissima scoperta matematica ma più che altro, metterebbe a rischio l'intero sistema delle connessioni sicure e controllo accessi.

Ora, la cosa curiosa è che ad appena 2 settimane dalla notizia del giovane Rubens, oggi mi imbatto in questa notizia di ieri dove un professore pluripremiato di matematica, afferma di aver fatto la stessa scoperta di Rubens. Caspita, due geni in due settimane, oppure non è una coincidenza ??
Il piccolo ha detto di non voler divulgare la sua scoperta poiché temeva che avrebbe potuto nuocere e che l'avrebbe inoltrata a dei matematici per le dovute verifiche.
Cosa sia successo dopo, non è dato saperlo e non ho trovato un gran che.

Il nostro Rubens dal canto suo, ha sviluppato una APP disponibile su Play Store per Android, che si chiama "Calcolo dei numeri primi". Io l'ho scaricata (gratis) e installata. Questa app permette di inserire un intervallo, per esempio da 5 a 50, entro cui trovare tutti i numeri primi.
Io ho fatto la verifica e sembra funzionare.
La cosa si fa interessante quando mettete da 5 a 1'000'000 . Il programmino resta occupato per circa mezzo minuto e poi in tutta tranquillità stampa a schermo una lunghissima lista di numeri, appunto da 5 a quasi 1 milione.
Non so se siano davvero primi, e non sono in grado di verificare se manchino alcuni numeri.
Chiedo quindi a qualche matematico / appassionato di dire la sua in proposito, sull'entità della scoperta e le eventuali implicazioni.
Sono comunque sorpreso e intenerito dalla brillante intelligenza di questo ragazzo, speriamo sia in buone mani !






Grazie !

Ciao. Non capisco cosa ci sia di difficile nel calcolare un numero primo (o una lista di n numeri primi) anche tramite algoritmi. Hai qualche riferimento al riguardo? Grazie.

Quello che è difficile, e mi risulta non sia ancora stato fatto, è realizzare una funzione che abbia come risultato tutti i numeri primi e solo numeri primi.

Cioè, una funzione f(n) dove dato n numero intero positivo non nullo f(n) restituisca l'n-esimo numero primo.

Se il ragazzo ha realizzato questo è un genio.

Poi siamo daccordo che tramite algoritmi e potenza di calcolo si possono calcolare tanti numeri primi quanto tempo e potenza di calcolo permettono. Ma è tutt'altra cosa rispetto ad avere una funzione.

Ciao DanieleSpace, ho dato una rapida occhiata, magari prendendomi un po' di tempo scriverò un commento più articolato, intanto faccio solo qualche precisazione di massima. Intanto i primi numeri primi (mi si scusi il bisticcio) sono 2,3,5,7,11,13... e quindi 1 è escluso, 2 incluso. In secondo luogo il professore del tuo link non dichiara di aver fatto la stessa scoperta del giovane calcabrese, ma di aver dimostrato l'ipotesi di Riemann, che è sì collegata ai numeri primi, ma ha un'importanza tutta propria e mi sento di dubitare che il ragazzino sia in grado anche solo di comprendere di cosa si tratti, perchè richiede conoscenze matematiche superiori. In ogni caso, che questa dimostrazione sia effettivamente stata trovata o meno, le cose non cambierebbero granchè a livello pratico perchè normalmente si assume che l'ipotesi di Riemann sia vera, già questo particolare nome, "ipotesi", è assai singolare in ambito matematico perchè tecnicamente quella di Riemann sarebbe una congettura, cioè un teorema non dimostrato, ma tanta è la venerazione nei confronti di Riemann che le sue congetture sono considerate direttamente ipotesi.

Tornando al ragazzino, beh, se davvero avesse trovato una formula che produce in sequenza tutti e soli i numeri primi, sarebbe forse il più straordinario risultato della teoria dei numeri. Però che voglia tenere segreta la scoperta mi insospettisce un po', unitamente al fatto che la sua app ci metta una trentina di secondi a sfornare l'elenco dei numeri primi minori di 1000000 (sono 78498), quando il mio computer ci mette circa un secondo a trovarli fino a 100 000 000 (sono 5761455) usando un algoritmo basato sul crivello di Eratostene. E' vero che ho un buon computer, però insomma, la cosa mi sembra comunque strana...

Franzeta,

grazie mille per le precisazioni. Il fatto che la app ci metta mezzo minuto può voler dire tante cose o nulla, il fatto è che crea un file di testo e scrive tutti i 78'498 numeri che solo a scorrere col dito ci vogliono minuti interi...e io ho installato la app sul cellulare, che ha una potenza di calcolo inferiore a un buon PC.
Quindi il tempo lungo è forse dovuto al modo in cui viene creato il file di testo.
Sarebbe comunque assurdo pretendere che il ragazzino abbia persino cercato di ottimizzare le performances del suo programmino :wink:
Andrò a rivedermi cosa diceva l'ipotesi di Riemann intanto...

@DanieleSpace

Eh ma sai, se hai una formula che ti genera tutti i numeri primi della forma f(n), come diceva @mg, anche col telefonino il calcolo dovrebbe essere pressoché immediato. Ma quello che forse non è stato chiarito abbastanza è che sarebbe come se il tredicenne in questione avesse scoperto la fusione fredda, come tipologia di risultato.

PS nel tuo link quando si parla di funzione Zeta di Riemann l'espressione è sbagliata.

EDIT In effetti se la app è scaricabile non dovrebbe essere difficile capire che algoritmo utilizza, e di conseguenza se c'è dietro una formula magica. Altrimenti una controprova sarebbe fargli cercare un particolare numero primo, molto grande, e vedere quanto tempo ci mette, per esempio il numero primo 10^15 +1 della successione. Se sta lì una settimana a calcolare vuol dire che non c'è nessuna formula magica.

Capito. Non sapendo come è il suo programmino, potrebbe essere come tutti gli altri e quindi il fine reale del ragazzino potrebbe anche essere il cercare clicks/installazioni per la sua app. Certo che se avesse inventato una formula che calcola istantaneamente ogni n primo, sarebbe una gran scoperta che non sarebbe da nascondere di certo.

Ciao a tutti:

Una funzione ha una variabile indipendente, e il ragazzo avrebbe potuto dire qual'é anche senza rivelare la formula. Supponiamo che sia un numero appartenente all'insieme dei numeri naturali. In tal caso, se fosse una funzione, il programma dovrebbe semplicemente chiedere: "Vuoi sapere qual'è l'n-esimo numero primo?"
Visto che così non è dubito che sia una funzione, ma se vuoi fare la prova chiedi alla app di cercare tutti i numeri primi tra 1 miliardo e 1 miliardo e 100. Se ci mette 30 secondi non è una funzione ma un algoritmo (magari ben fatto, ma una funzione è un'altra cosa).

Franzeta

Eh ma sai, se hai una formula che ti genera tutti i numeri primi della forma f(n), come diceva @mg, anche col telefonino il calcolo dovrebbe essere pressoché immediato.

Concordo, ma dal punto di vista informatico, un conto è generare i numeri con l'unità logica aritmetica del processore, un altro conto è stampare tutti i numeri a schermo in un file di testo, per esempio con un comando tipo printf(); .
Non sappiamo come è stato scritto il programma, ovviamente sarebbe bello vedere il codice e quindi la formula (presunta) magica.

Ma quello che forse non è stato chiarito abbastanza è che sarebbe come se il tredicenne in questione avesse scoperto la fusione fredda, come tipologia di risultato.

Anche qui mi trovi d'accordo. È proprio per questo che ho pensato di condividere la notizia. Facciamo un breve ragionamento. Metti caso che davvero abbia trovato il Santo Graal della matematica e quindi una super-scorciatoia per la crittografia.
Che cosa ci aspettiamo che dicano:
1. Accidenti, siamo davvero sorpresi, ora tutta la crittografia del mondo è in pericolo e la matematica avrà nuove frontiere, grazie a un bambino calabrese
2. Il bambino è intelligente ma l'algoritmo non funziona bene, lo conoscevamo già, è una variante del Crivello di Eratostene ( o qualcosa di simile). Peccato, complimenti comunque, gli diamo una borsa di studio e 5 minuti di trasmissione TV a Porta a Porta con Vespa

Dato che qui siamo in un sito di "complottisti", "terrapiattisti" con la carta stagnola in testa :wink: , direi che a prescindere che l'algoritmo funzioni o meno, a noi verrà detto che non funziona. Almeno che non si possa davvero fare una pubblica discussione, in trasparenza e serenità. Ma tra tutti i temi controversi che potrebbero cambiare il destino dell'umanità (come la fusione fredda che hai citato), tu quante discussioni trasparenti hai visto ?

Altrimenti una controprova sarebbe fargli cercare un particolare numero primo, molto grande, e vedere quanto tempo ci mette, per esempio il numero primo 10^15 +1 della successione.

Purtroppo il programmino è strutturato in modo un po' basic e il prompt per inserire i numeri minimo e massimo tra cui cercare i primi, non permette più di una decina di caratteri.
Se provo a cercare i primi intorno al miliardo, il programmino va in crash. Ma anche questo dipende da come è stata riservata la memoria per le variabili di entrata: (integer, small_integer, ecc. ).
Al momento non è quindi fattibile...

Aggiungo che sono incappato in questa storia da poco e non ho ancora avuto tempo di approfondire. Vorrei solo sottolineare che vale la pena seguire il ragazzo e la vicenda. Appena so qualcosa, aggiorno il thread.
Ah dimenticavo, non è affatto detto che il programmino sia fatto con l'ultima scoperta del ragazzo. Potrebbe aver fatto la scoperta successivamente e questo programma essere un precursore...Intanto se davvero ha fatto tutto lui, direi che è già notevole.

scusate ma finchè non si fan le cose alla luce del Sole... il bambino potrebbe essersi limitato a compilare un programmino che da un file di testo con la lista dei numeri primi te li stampa a video a seconda dell'intervallo che vuoi tu :hammer:

o mi son perso qualcosa? il fatto che ci siano limiti per i valori d'ingresso puzza un po'...

il bambino potrebbe essersi limitato a compilare un programmino che da un file di testo con la lista dei numeri primi te li stampa a video a seconda dell'intervallo che vuoi tu

È possibilissimo, non si può escludere. Per questo trovo sia utile cercare di raccogliere informazioni sul tema, che ritengo comunque interessante.
Se mi avanza un po' di tempo, proverò a contattare lui o i suoi genitori, per sapere qualcosa di più, senza essere troppo invadente.

C'è poi una parentesi un po' triste... sulla pagina FB dove era apparso il suo video, un sacco di ragazzini hanno postato commenti denigratori o ironici del tipo "Oh , ma non ti piace la figa come a tutti gli altri ?", oppure "Secchione", "nerd", e simili.

VI CHIEDO SCUSA :baby:

Il link corretto dove viene spiegata la questione è questo:

www.iene.mediaset.it/video/rubens-genio-...a-sfida_173888.shtml

Correggo post iniziale

Aggiungo qualche considerazione, partendo da qui:

DanieleSpace ha scritto: C'è poi una parentesi un po' triste... sulla pagina FB dove era apparso il suo video, un sacco di ragazzini hanno postato commenti denigratori o ironici del tipo "Oh , ma non ti piace la figa come a tutti gli altri ?", oppure "Secchione", "nerd", e simili.

A questo proposito, parlando del quesito matematico che pone alla fine del video, direi che non c'è niente di straordinario rispetto a quelle che dovrebbero essere le conoscenze matematiche di un quattordicenne che ha 9 in matematica, se non il fatto che a quella giovanissima età dovrebbe ancora valere l'equazione seno = tette. Poi che venga un po' preso in giro ci può anche stare, insomma, nessuno gli ha imposto di cercarsi questa notorietà tramite le Iene.

Veniamo ora alla sua formula magica. Innanzitutto chiariamo che una funzione è un algoritmo, quindi in effetti di funzioni f(n) che elencano tutti i numeri primi ce ne sono già parecchie note. Ad esempio quella implementata dal programma Euler che ho usato per il mio primo commento qui sopra: la funzione usa il crivello di Eratostene come subroutine ed effettivamente produce in sequenza tutti i numeri primi, quindi se gli chiediamo di calcolare l'n-esimo numero primo, prima o poi, ci arriva. Quanto possa essere distante questo "poi" è il problema vero. Detto altrimenti: una funzione f(n) che genera l'n-esimo numero primo è quella che ha come subroutine la funzione che ho usato io, e scarta tutti i numeri primi trovati meno l'ultimo.

Il problema è che non è nota alcuna funzione che abbia invece queste due caratteristiche:

1) Sia in grado di generare l'n-esimo numero primo senza dover generare i precedenti;
2) Sia data dalla composizione e/o iterazione di funzioni elementari.

Posso fare un esempio particolarmente calzante. Per la successione di Fibonacci una tale formula esiste, eccola:



Dove Φ è la sezione aurea. Questa formula, oltre che elegante, è molto utile, dato che se si volesse calcolare F_n per ricorsione ci si troverebbe davanti ad un problema di rapida esplosione del numero di passaggi, di fatto anche il migliore computer non arriverebbe a calcolare il millesimo numero di Fibonacci. La formula qui sopra soddisfa chiaramente le richieste 1) e 2), ed è quello che ci aspettiamo da una formula magica come quella che sostiene di aver trovato il ragazzino. Un altro esempio chiarificatore è quello della formula che dà il numero delle partizioni di un numero naturale n, è stata trovata dal genio matematico Ramanujan all'inizio del '900 ed è la seguente:



Ramanujan sosteneva che la formula gli fosse stata dettata in sogno dalla dea Kalì, da matematico non posso far altro che credergli...si noti che anche Ramanujan fu fra quelli che cercarono invano l'analoga formula per i numeri primi, giusto per rimarcare il livello di difficoltà del problema, ma a quanto pare in questo caso la dea non si fece viva in sogno.

Torniamo alla formula magica del ragazzino. Un punto che mi lascia perplesso dell'intervista è che afferma di non voler inviare la formula all'Unione Matematici Italiani, ma preferisce "parlarne faccia a faccia". Fin qui ci può anche stare, magari ha paura che qualcuno gli voglia rubare la scoperta, anche se dopo la pubblicità che si è fatto sarebbe alquanto difficile, aggiungo anche che in genere non ci sono discussioni sulla priorità di un risultato, ma solo sulla sua correttezza, si veda ad esempio la vicenda della dimostrazione dell'ultimo teorema di Fermat da parte di Andrew Wiles. O meglio: non ci sono discussioni sulla priorità a meno che non ci siano fondate prove che dimostrano che due matematici hanno raggiunto indipendentemente lo stesso risultato, nel qual caso si accreditano entrambi della scoperta. Quello che però mi lascia molto perplesso e che poi il ragazzo aggiunge che non vuole rendere nota la dimostrazione, perchè quella la sa solo lui. Probabilmente vuole svelare anche quella "faccia a faccia".

A perplimermi sono diversi aspetti dilettanteschi, che per carità ci stanno tutti in un quattordicenne, ci stanno però meno in un quattordicenne che ha trovato il Santo Graal della teoria dei numeri. Punto primo, aspetto organizzativo: ma in che senso vuole parlarne faccia a faccia? Non esiste mica il Signor Unione Matematici Italiani, al massimo può parlarne con qualche professore universitario che funge da rappresentante della comunità matematica, ma in ogni caso un risultato del genere andrebbe sottoposto alla verifica dell'intera comunità, non di qualche persona seduta in una stanzetta.

Punto secondo, più tecnico e importante: nota la formula f(n), salvo complicazioni che però in questo momento non riesco ad immaginare, dovrebbe essere semplice dimostrarla per induzione ( qui trovate un esempio di dimostrazione per induzione che avevo fatto per altri scopi), ma, mi viene di aggiungere, questo tipo di dimostrazione non dovrebbe essere noto ad un quattordicenne, a meno che non si sia fatto dosi pesanti di testi matematici avanzati per la sua età. Quello che sto dicendo è che se gli dai una formula f(n), che verifichi i punti 1) e 2) qui sopra, credo che ogni matematico del mondo sia in grado di dimostrarla per induzione, il problema dell'induzione matematica è che funziona solo se sai già qual è la formula corretta, ma non aiuta in nessun modo a trovarla.

Ecco allora che questa segretezza posta sulla dimostrazione mi risulta difficile da giustificare, anche perchè un risultato matematico senza dimostrazione non è un risultato matematico, ma solo una congettura, quindi nascondendo la dimostrazione il ragazzo sarebbe accreditato per la scoperta della formula ma non per la sua dimostrazione, che andrebbe attribuita al più svelto fra i matematici che avessero comunicazione della formula magica. Comunque quello che mi sento di dire è che se davvero c'è questa formula magica, non passerà molto tempo prima che sia divulgata pubblicamente, in caso contrario significa che si è trattato di un abbaglio. Non metterei troppa enfasi sul problema della crittografia, dato che in quel caso non si tratta di generare al volo l'n-esimo numero primo, ma di fattorizzare numeri composti molto grandi, e la fattorizzazione richiede una ricerca fra tutti i numeri primi in un certo intervallo legato al numero da fattorizzare, questo per dire che la velocità degli algoritmi ostili alla crittazione aumenterebbe ma non in modo catastrofico.

Per concludere aggiungo che in effetti dagli anni '70 è nota una funzione, per di più polinomiale, in grado di generare tutti i numeri primi. Ha però tre grossi limiti: primo vuole come input 26 numeri interi, quindi si tratta di un polinomio che ha per variabili tutte le lettere dell'alfabeto; secondo non genera solo numeri primi, anche se questo problema è parzialmente mitigato dal fatto che quando non restituisce come risultato un numero primo allora si tratta di un numero negativo; ultimo e peggiore limite, non genera numeri primi in sequenza. Insomma, si tratta di una curiosità matematica di scarsa utilità pratica.

Ancora un paio di cose, che non avevo riportato nell'ultimo commento. Se fosse davvero nota la formula f(n) che produce l'n-esimo numero primo (secondo le prescrizioni 1) e 2) riportate in precedenza, non lo ripeto più), questa comporterebbe la risoluzione di due dei problemi aperti più importanti della teoria dei numeri. Il primo è la già citata ipotesi di Riemann, il secondo è la congettura dei numeri primi gemelli, che risale addirittura ad Euclide. Cioè stiamo parlando di quelli che sono con ogni probabilità il più difficile e il più longevo fra i problemi aperti della teoria dei numeri.

Ora, io personalmente credo che la formula f(n) non solo non sia stata trovata ancora da nessuno, ma che non esista proprio e che prima o poi qualcuno possa dimostrare questa non esistenza, così come è avvenuto per la formula risolutiva di equazioni di grado maggiore del quarto. Ma anche ammettendo che invece la formula esista, dovrebbe essere di una complicatezza estrema, quindi a mio avviso è impossibile per almeno due ordini di ragioni che sia stata trovata da un quattordicenne. Secondo me tutta la vicenda nasce da un fraintendimento: il ragazzo, avuta notizia che non è mai stata trovata nessuna formula f(n), ha forse pensato che non esistesse nessuna funzione in generale che calcolasse l'n-esimo numero primo, mentre come ho spiegato sopra di funzioni siffatte ne esistono a bizzeffe, il problema sono le ulteriori richieste 1) e 2).

@ Franzeta

Ok grazie mille, era esattamente il genere di approfondimento di cui c'era bisogno per chiarire il tema.