Per tutti coloro che se ne interessano, sto lavorando ad un mio progetto matematico che ha a che fare con i numeri primi.
Non troppo tempo fa, avevo scoperto (vi allego gli appunti appena posso) che i numeri primi si distribuiscono (eccezion fatta per 2 e 3) sulle rette 6x+1 e 6x-1 (x numero naturale, ovverossia 1, 2, 3 ecc).
Sebbene questo fosse vero, c’erano dei salti riguardo i numeri primi, calcolabili, ma comunque dispendiosi di memoria.
Avevo in pratica sviluppato un crivello, migliore di quello di Erastotene, ma abbastanza dispendioso di ram.
Oggi invece, mettendomi un pò a lavoro con un nuovo metodo, ho scoperto un nuovo crivello, facilissimo da implementare e molto potente. A differenza di quello di Erastotene, e di quello di Atkin, funziona in modo tale da sapere in precedenza la posizione del numero da scartare, e progredire fino ad un limite dato.
Non sarà forse utile per il calcolo di numeri di Mersenne, tuttavia mi sembra ottimo e veloce per un qualunque altro impiego.
Aspetto un pò prima di pubblicarlo, per approfondire lo studio e correggere eventuali errori e/o anomalie, dopodichè pubblicherò i miei appunti 
Buona notte a tutti!
M’interesso da tempo di numeri primi e quindi leggerò con interesse il suo lavoro.
Intanto posso dirle che ho trovato dell’epressioni matematiche che consentono di determinare, dati i primi n numeri primi, l’n+1° numero primo ed i successivi entro il quadrato dell’n+1° numero primo.
Le dò un esempio:
noti 2 e 3 da:
1+2(x+int((x+1)/2)
si ottengono il 5 ed i successivi numeri primi entro il quadrato di 5.
L’espressione è generalizzabile.
Se i numeri primi sono determinabili attraverso un’espressione matematica vuol dire che esiste una regolarità nella loro successione, contrariamente a quanto generalmente si crede.
Buon lavoro.
Pietro Di Paolo
Gent.mo Alessio,
va benissimo il tu.
Mi chiedi come funziona l’algoritmo che ho inserito nel tuo blog.
Ti riscrivo l’algoritmo che ti ho inviato:
1 + 2[x + int(x+1)/2]
Mi chiedi se al posto di x devi mettere un numero primo.
No.
Si tratta di una normale funzione del tipo Y= f(x) in cui la variabile x può assumere tutti i valori nell’ambito degl’insieme degli interi.
La funzione dà come primo termine il 5 ed i termini successivi sono numeri primi (P) entro il limite del quadrato di 5.
Se non si pone tale limite, l’algoritmo dà una successione di numeri non divisibili per 2 e per 3.
La variabile che hai inserito: 260.849 dà effettivamente 782.549 che non è divisibile né per 2, né per 3 com’è facilmente verificabile.
Questo algoritmo fa parte di una famiglia di formule che, dati i primi n P, danno l’(n+1)° P ed i successivi entro il quadrato di quest’ultimo.
Ti dò il 2° algoritmo:
(3+x)° P = 1+ 2(x+int(x+7)/8+int(x+1)/8 + int((x+int(x+7)/8 + int(x+1)/8)+1)/2) per x>0
dà come primo termine il 7, i termini successivi sono P entro il limite del quadrato di 7.
Se si prosegue oltre tale limite si ha la successione di numeri non divisibili per 2, per 3 e per 5.
Fa la differenza tra il secondo ed il primo termine, tra il terzo ed il secondo, e così via, sia per il primo che per il secondo algoritmo, scoprirai cose interessanti.
Inoltre, come puoi osservare, il secondo algoritmo si ricava dal primo; infatti sostituendo alle variabili del 1° algoritmo l’espressione: x+int(x+7)/8+int(x+1)/8 si ricava il secondo.
Il procedimento di creazione degli algoritmi di cui ti ho dato due esempi: uno per n=2 e l’altro per n=3, dà luogo ad espressioni rapidamente più complesse.
Sulla base di quanto sopra ho elaborato un modo per definire un algoritmo che supera questa difficoltà ed è relativamente più semplice.
Infine mi chiedi cosa mi ha spinto ad ideare questi algoritmi.
Tutto è cominciato da una passeggiata.
Incontrando una cava di sabbia vidi lavorare un vaglio che separava la sabbia dalla giaia e mi venne in mente il crivello di Eratostene che, invece, separava i numeri primi dai multipli.
Nel crivello se si eliminano i numeri divisibili per 2 si hanno i numeri dispari, cioè numeri esprimibili mediante una formula.
Se si eliminano anche i numeri non divisibili per 3 si otteneva una successione di numeri non divisibili per 2 e per 3.
Allora mi sono posto un’altra domanda.
Quella successione era esprimibile in una formula?
La risposta è il primo algoritmo che ti ho proposto.
Il resto ha richiesto tempo, ma la strada era ormai aperta.
In questo periodo sto lavorando ad un altro problema per il quale ho bisogno di una tavola di numeri primi tra 10000 e 100000.
Puoi aiutarmi?
Cordiali saluti,
Pietro Di Paolo
auguri per il tuo crivello, ma dubito che possa avere un grande successo.
correzione errore
Nella prima e.mail che ti ho inviato l’espressione:
x + int(x+7)8 + int(x+1)/8 è errata.
Quella esatta è: x+ int((x+7)8) + int((x+1)/8).
La funzione int si riferisce necessariamente ai rapporti che possono essere frazionari, mentre riferita ai numeratori non ha senso dal momento che gli stessi sono degli interi.
Tenendo conto di quanto sopra il 2° algoritmo (3+x)° P dev’essere scritto come segue:
1+2(x+int((x+7)/8)+int((x+1)/8)+int((x+int((x+7)/8)+
+int((x+1)/8)+1)/2))
oppure, poiché vi sono espressioni ripetute si può porre:
x + int((x+7)/8) + int((x+1)/8) = G
trasformando l’algoritmo in:
(3+x)°P=1+2(x+ int((x+7)/8)+int((x+1)/8)+int((G + 1)/2))