venerdì 2 marzo 2007

Creatività

Da quando hanno saputo che la EFF offre un premio di 100.000 dollari alla prima persona che scopre un numero primo composto da almeno un milione di cifre, i miei studenti di seconda sono dediti alla ricerca di numeri primi.

Ricerca che avviene in modo assolutamente casuale: prendono un numero primo, provano ad aggiungere qualche cifra, controllano un po' che il numero risultante non sia divisibile per 2, 3, 5, e dichiarano di aver trovato un nuovo numero primo. Ho provato a spiegare che con questo metodo non si arriva a un milione di cifre in breve tempo, che le tecniche per verificare se un numero così grande è primo non sono quelle standard, perché non si può verificare la divisibilità di quel numero con tutti i numeri primi che lo precedono, ma non c'è stato niente da fare.

L'altro giorno uno studente mi annuncia di aver trovato un numero primo colossale. Allora estraggo la mia calcolatrice e provo a vedere se è vero. Inserisco il numero, dico alla calcolatrice di fattorizzarlo, e attendo. Gli studenti mi guardano meravigliati:

“Prof, ma la sua calcolatrice riesce a calcolarlo?”.
“Certo”.
“Ma le dice se un numero è primo o no?”.
“Bè, se non è primo, me lo scompone”.
“Ma quella calcolatrice fa tutto?”.
“Certo”.
“Ma riesce anche a...”.
“Certo”.
“Prof, dove l'ha comprata?”.

Dopo un po' di tempo (almeno una decina di secondi), la calcolatrice restituisce il risultato: il numero è composto da due fattori primi, uno di cinque o sei cifre, l'altro più grande. È andata male, ma neanche tanto.

“Prof, mi presta la calcolatrice?”. Hanno provato a cercare qualche numero primo col loro metodo spannometrico, e ne hanno trovato qualcuno. Il record: 496311972439362137.

Se lo avessi dato per compito, mi avrebbero guardato con aria di compatimento...

6 commenti:

Anonimo ha detto...

bè, chi si mette a fare ricerche per un compito per cui al massimo avrrà un + sul registro? comunque aver trovato un numero primo non mi sembra si possa definire "creatività"

professore ha detto...

È il metodo "inusuale" che mostra qualche barlume di attività personale. Per una volta, non hanno cercato su internet...

Ronkas ha detto...

adesso me lo scrivo in c++,
però temo che dovrò lasciare il computerino acceso per quache tempo...


però bah con gli strumenti che abbiamo oggi vuoi dire che un qualche furbone con un cluster professionale non si sia già messo lì a calcolarlo?

professore ha detto...

Bè, certo che l'hanno fatto. E quale cluster più grande di tutta internet? Del resto, il numero non è da calcolare, è da trovare (il che è molto peggio). Fai un salto a www.mersenne.org.

Anonimo ha detto...

immagino che lei conosca un modo per trovare un numero con 1 milione di cifre che potrebbe essere primo in poco tempo,vero?

Ronkas ha detto...

ma adesso che ci penso...
ma per trovare il primo numero primo con almeno un milione di cifre non basterebbe applicare un filtro di non mi ricordo cosa (si applica a una schacchiera 10x10 contenente il primo centinaio) ad un numero che abbia almeno 1 milione di cifre?

perciò 1000(tanti zeri q.b.)

o comunque sapendo il minor numero a un milione di cifre non basterebbe far lavorare partendo da quella cifra un algoritmo brute-force?