giovedì 29 dicembre 2011

Crivelli — 3: contare i punti su una griglia

«Allora, dobbiamo astrarre il crivello di Eratostene?».

«Esatto. Ragioniamo in questo modo: cosa significa che un numero è primo?».

«Che ha solo due divisori distinti, giusto?».

«Ottimo, vedo che ti ricordi».

«Certo che mi ricordo!».

«Va bene. Quindi un numero che non è primo ha più di due divisori distinti».

«Certo».

«Quindi i numeri primi sono tali per cui l'equazione xy = p ha due sole soluzioni».

«Ecco che complichiamo…».

«Eh, sì. Mentre per i numeri non primi l'equazione xy = p ha più di due soluzioni».

«Aspetta un momento: dici che per i numeri primi quell'equazione ha solo due soluzioni perché puoi scambiare di posto x e y, vero? Cioè, 7 è uguale a 1 moltiplicato 7 oppure a 7 moltiplicato 1. Ho capito bene?».

«Hai capito benissimo. Ora, che curva è quella che ha equazione xy = p, con p costante, x e y variabili?».

«Una… iperbole?».

«Ottimo. Allora guarda come ti traduco la definizione di numero primo: un numero p è primo se esistono solo due punti a coordinate intere positive che appartengono all'iperbole xy = p».

«Mamma mia, che depravazione mentale. Comunque è giusto, sì».

«E, al contrario del mio prof di geometria, io ti faccio anche un disegno, con = 5».



«Bello, hai disegnato la griglia dei numeri interi».

«Già, come vedi gli unici punti della griglia che vengono toccati dall'iperbole sono (1,5) e (5,1)».

«Carino».

«Se invece il numero non è primo, i punti che vengono toccati sono più di due. Ecco per esempio xy = 12».



«Sei punti».

«Sì, saranno sempre in numero pari, a causa della simmetria; a meno che il numero non sia un quadrato: in quel caso sono dispari».

«Ok. Fin qua ci sono».

«Bene, allora diciamo che il crivello di Eratostene funziona contando i numeri interi positivi che sono soluzioni dell'equazione xy = p, o, per dirla come dicono i Veri Matematici, funziona analizzando i valori della forma quadratica riducibile xy».

«Ed ecco l'astrazione incomprensibile. I Veri Matematici fanno almeno la figurina dell'iperbole, per fare capire di cosa si sta parlando?».

«Naturalmente no».

«Capirai».

«E ora che abbiamo astratto, ragioniamo in questo modo: potremmo forse cambiare la forma quadratica che stiamo utilizzando, per velocizzare un po' i conti?».

«Boh? Possiamo?».

«Possiamo, ma complichiamo. La semplicità del crivello si perde un po'».

6 commenti:

Anonimo ha detto...

Cappero! Queste cose mi sarebbero servite assai nel 1985 e dintorni! :-)
Grazie per questi bei post!

zar ha detto...

Cosa combinavi nel 1985...?

Marco Panino ha detto...

Facile facile questo passaggio. L'ho capito pure io.

valerio ha detto...

Precisazione stupida, ma se il numero è un quadrato i punti in questione sono in numero dispari.

zar ha detto...

Uh, è vero! Correggo subito...

Anonimo ha detto...

@zar
facevo il liceo scientifico e mi cimentavo in algoritmi in basic per la scomposizione in fattori.