Ricerca Numeri primi metodo dimensione
Buon giorno
Mi chiamo Claudio Govi e vorrei postare una mia teoria sulla ricerca dei numeri primi.
Questa teoria si basa sulla ricerca di questi numeri dentro una dimensione finita e non su un numero solo. Non sono un matematico, sono un programmatore, e spero mi scuserete se il mio linguaggio non sraò molto matematico
Per dimensione finita intendo la distanza che c’è tra un due numeri dispari consecutivi elevati al quadrato. Questa distanza la si può calcolare sulla base di 8 perché la distanza minima tra due numeri dispari consecutivi è (3^2-1^2= 8) e si incrementa di 8 in 8, per cui ogni numero di (8^n) rappresenta la distanza tra due numeri dispari consecutivi.
Diciamo che la mia dimensione di X sia uguale a 200 ((200+4)/4)=51 perciò avrò (51^2 - 49^2).
In questa dimensione di 200 e cioè da 2401 a 2601 ci saranno racchiusi tutti i divisori primi da 2 a 51 e cioè 2-3-5-7-11-13-17-19-23-29-31-37-41-43-47
Eliminando da questa dimensione tutti i numeri pari e i due numeri al quadrato 2401 e 2601, otterremo 99 numeri dispari tra cui ci saranno i potenziali numeri primi che noi dovremo individuare, e i nostri divisori diventeranno 3-5-7-11-13-17-19-23-29-31-37-41-43-47.
Per scoprire quali numeri dispari di questi 99 sono primi dovrò interrogare tutti i 14 divisori primi e se nessuno di questi dividerà il numero preso in esame questo sarà un numero primo.
Facciamo un esempio…
2401+2=2403 divisore 3
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+4=2405 divisore 5 - 13 - 37
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+6=2407 divisore 29
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+8=2409 divisore 3 - 11
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+10=2411 divisore nessuno
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+12=2413 divisore 19
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+14=2415 divisore 3 - 5 - 7 - 23
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+16=2417 divisore nessuno
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+18=2419 divisore 41
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
Etc… fino al numero 2401+198
Ora. Rimanendo nella dimensione di X=200 proviamo ad analizzare una sotto dimensione di sole 5 unità
2401+2=2403 divisore 3
2401+4=2405 divisore 5 - 13 - 37
2401+6=2407 divisore 29
2401+8=2409 divisore 3 - 11
2401+10=2411 divisore nessuno
In questa sotto dimensione che chiameremo Y, poniamo Y=10, analizziamo i divisori e vediamo che di questi 14 divisori contenuti nella dimensione X=200, in questa sotto dimensione Y=10, ne troviamo solo 6. 3-5-11-13-29-37.
La domanda è… E se io per testare questi numeri dispari da 2401+2 a 2401+10 avessi usato solo quei 6 divisori, anziché 14, sicuramente ci avrei messo meno tempo e avrei avuto lo stesso risultato e cioè scoperto che il numero 2401+10 è un numero primo.
Come faccio a sapere quali divisori nella sotto dimensione Y=10 soddisfano la mia ricerca?
Mi faccio aiutare dalla funzione Modulare in questo modo.
A=2401 Mod(3)=1
Utilizzo il modulo per definire se A è dispari o pari A Mod(2)
se A Mod(2)=0 B=(-A)+3*2
se A Mod(2)<>0 B=(-A)+3
Se B
A=2401 Mod(5)=1
se A Mod(2)=0 B=(-A)+5*2
se A Mod(2)<>0 B=(-A)+5
Se B
A=2401 Mod(7)=0
se A Mod(2)=0 B=(-A)+7*2
se A Mod(2)<>0 B=(-A)+7
Se B
Etc… Fino a interpellare tutti i 14 divisori primi della dimensione X=200
Alla fine otterrò un file dei soli divisori che interessano alla sotto dimensione di Y=10, dopo di ché sarà molto facile stabilire entro questa sotto dimensione quali numeri sono primi e quali sono composti.
Vi lascio qui sotto i dati degli esperimenti fatti su 1.320.690.920 divisori, solo numeri primi, in una dimensione totale di 30.499.999.951^2 – 30.499.999.949^2 = 121.999.999.800
ora inizio = 11:18:28.881923
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
930249996889000002689
930249996889000002697
930249996889000002701
930249996889000002707
930249996889000002767
930249996889000002829
930249996889000002877
930249996889000002977
930249996889000003037
930249996889000003061
930249996889000003091
930249996889000003259
930249996889000003289
930249996889000003309
930249996889000003319
930249996889000003327
930249996889000003339
930249996889000003483
930249996889000003543
930249996889000003577
Numero divisori primi interpellati 1.320.690.920
ora fine = 11:49:03.758468
Divisori utilizzati 776 Su 1.320.690.920 totali in una sotto dimensione di Y=1.000
Da N= 930249996889000002601 a N+Y 930249996889000003601
Trovati 20 Numeri primi
Solo in questa prova vi posto tutti i numeri primi trovati, per le altre prove non avrei abbastanza spazio per postarle.
--------------------------------------------------------------------------------------------
ora inizio = 12:35:11
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
Numero primi letti 1.320.690.920
ora fine = 13:06:25
Divisori utilizzati 5895 Su 1.320.690.920 totali, in una sotto dimensione di Y=10.000
Da N= 930249996889000002601 a N+Y 930249996889000012601
Trovati 217 Numeri primi
---------------------------------------------------------------------------------------------
ora inizio = 13:14:20
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
Numero primi letti 1.320.690.920
ora fine = 13:44:42
Divisori utilizzati 45427 Su 1.320.690.920 totali, in una sotto dimensione di Y=100.000
Da N= 930249996889000002601 a N+Y 930249996889000102601
Trovati 2084 Numeri primi
----------------------------------------------------------------------------------------------------
Questo è l’algoristmo scritto in Python
dove divi=Divisore, dove ni= 930249996889000002601
div1=ni%divi
if div1%2==0:
div2=(-div1)+divi*2
else:
div2=(-div1)+divi
if div2<=massimo:
scrivi.write(str(divi)+'\n')
Grazie
Mi chiamo Claudio Govi e vorrei postare una mia teoria sulla ricerca dei numeri primi.
Questa teoria si basa sulla ricerca di questi numeri dentro una dimensione finita e non su un numero solo. Non sono un matematico, sono un programmatore, e spero mi scuserete se il mio linguaggio non sraò molto matematico
Per dimensione finita intendo la distanza che c’è tra un due numeri dispari consecutivi elevati al quadrato. Questa distanza la si può calcolare sulla base di 8 perché la distanza minima tra due numeri dispari consecutivi è (3^2-1^2= 8) e si incrementa di 8 in 8, per cui ogni numero di (8^n) rappresenta la distanza tra due numeri dispari consecutivi.
Diciamo che la mia dimensione di X sia uguale a 200 ((200+4)/4)=51 perciò avrò (51^2 - 49^2).
In questa dimensione di 200 e cioè da 2401 a 2601 ci saranno racchiusi tutti i divisori primi da 2 a 51 e cioè 2-3-5-7-11-13-17-19-23-29-31-37-41-43-47
Eliminando da questa dimensione tutti i numeri pari e i due numeri al quadrato 2401 e 2601, otterremo 99 numeri dispari tra cui ci saranno i potenziali numeri primi che noi dovremo individuare, e i nostri divisori diventeranno 3-5-7-11-13-17-19-23-29-31-37-41-43-47.
Per scoprire quali numeri dispari di questi 99 sono primi dovrò interrogare tutti i 14 divisori primi e se nessuno di questi dividerà il numero preso in esame questo sarà un numero primo.
Facciamo un esempio…
2401+2=2403 divisore 3
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+4=2405 divisore 5 - 13 - 37
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+6=2407 divisore 29
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+8=2409 divisore 3 - 11
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+10=2411 divisore nessuno
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+12=2413 divisore 19
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+14=2415 divisore 3 - 5 - 7 - 23
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+16=2417 divisore nessuno
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
2401+18=2419 divisore 41
3-5-7-11-13-17-19-23-29-31-37-41-43-47.
Etc… fino al numero 2401+198
Ora. Rimanendo nella dimensione di X=200 proviamo ad analizzare una sotto dimensione di sole 5 unità
2401+2=2403 divisore 3
2401+4=2405 divisore 5 - 13 - 37
2401+6=2407 divisore 29
2401+8=2409 divisore 3 - 11
2401+10=2411 divisore nessuno
In questa sotto dimensione che chiameremo Y, poniamo Y=10, analizziamo i divisori e vediamo che di questi 14 divisori contenuti nella dimensione X=200, in questa sotto dimensione Y=10, ne troviamo solo 6. 3-5-11-13-29-37.
La domanda è… E se io per testare questi numeri dispari da 2401+2 a 2401+10 avessi usato solo quei 6 divisori, anziché 14, sicuramente ci avrei messo meno tempo e avrei avuto lo stesso risultato e cioè scoperto che il numero 2401+10 è un numero primo.
Come faccio a sapere quali divisori nella sotto dimensione Y=10 soddisfano la mia ricerca?
Mi faccio aiutare dalla funzione Modulare in questo modo.
A=2401 Mod(3)=1
Utilizzo il modulo per definire se A è dispari o pari A Mod(2)
se A Mod(2)=0 B=(-A)+3*2
se A Mod(2)<>0 B=(-A)+3
Se B
A=2401 Mod(5)=1
se A Mod(2)=0 B=(-A)+5*2
se A Mod(2)<>0 B=(-A)+5
Se B
A=2401 Mod(7)=0
se A Mod(2)=0 B=(-A)+7*2
se A Mod(2)<>0 B=(-A)+7
Se B
Etc… Fino a interpellare tutti i 14 divisori primi della dimensione X=200
Alla fine otterrò un file dei soli divisori che interessano alla sotto dimensione di Y=10, dopo di ché sarà molto facile stabilire entro questa sotto dimensione quali numeri sono primi e quali sono composti.
Vi lascio qui sotto i dati degli esperimenti fatti su 1.320.690.920 divisori, solo numeri primi, in una dimensione totale di 30.499.999.951^2 – 30.499.999.949^2 = 121.999.999.800
ora inizio = 11:18:28.881923
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
930249996889000002689
930249996889000002697
930249996889000002701
930249996889000002707
930249996889000002767
930249996889000002829
930249996889000002877
930249996889000002977
930249996889000003037
930249996889000003061
930249996889000003091
930249996889000003259
930249996889000003289
930249996889000003309
930249996889000003319
930249996889000003327
930249996889000003339
930249996889000003483
930249996889000003543
930249996889000003577
Numero divisori primi interpellati 1.320.690.920
ora fine = 11:49:03.758468
Divisori utilizzati 776 Su 1.320.690.920 totali in una sotto dimensione di Y=1.000
Da N= 930249996889000002601 a N+Y 930249996889000003601
Trovati 20 Numeri primi
Solo in questa prova vi posto tutti i numeri primi trovati, per le altre prove non avrei abbastanza spazio per postarle.
--------------------------------------------------------------------------------------------
ora inizio = 12:35:11
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
Numero primi letti 1.320.690.920
ora fine = 13:06:25
Divisori utilizzati 5895 Su 1.320.690.920 totali, in una sotto dimensione di Y=10.000
Da N= 930249996889000002601 a N+Y 930249996889000012601
Trovati 217 Numeri primi
---------------------------------------------------------------------------------------------
ora inizio = 13:14:20
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
Numero primi letti 1.320.690.920
ora fine = 13:44:42
Divisori utilizzati 45427 Su 1.320.690.920 totali, in una sotto dimensione di Y=100.000
Da N= 930249996889000002601 a N+Y 930249996889000102601
Trovati 2084 Numeri primi
----------------------------------------------------------------------------------------------------
Questo è l’algoristmo scritto in Python
dove divi=Divisore, dove ni= 930249996889000002601
div1=ni%divi
if div1%2==0:
div2=(-div1)+divi*2
else:
div2=(-div1)+divi
if div2<=massimo:
scrivi.write(str(divi)+'\n')
Grazie
Risposte
Testo se è una potenza di un numero primo controllando che \( \left \lfloor n^{1/m} \right \rfloor^m = n \) per ogni \( 1 \leq m \leq \ln n \) (in tempo logaritmico)
"3m0o":
Testo se è una potenza di un numero primo controllando che \( \left \lfloor n^{1/m} \right \rfloor^m = n \) per ogni \( 1 \leq m \leq \ln n \) (in tempo logaritmico)
Questo non è un test di primalità e comunque viaggia in tempo polinomiale, non logaritmico.
Hydro ha scritto
Questo non è un test di primalità e comunque viaggia in tempo polinomiale, non logaritmico.
Daccordissimo
Leggendo il commento di Hydro mi sono reso conto di quanto sia posta male la mia domanda. Ci sono dei numeri che sono molto facili da fattorizzare e questi numeri sono i prodotti delle potenze. Nel caso di un quadrato la cosa diventa poi elementare. Negli altri casi N^n potrebbe essere molto grande ma a conti fatti sia N che n sono molto piccoli e facili da rintracciare. Sappiamo che tra i numeri ci sono quelli più facili da fattorizzare e altri molto più complicati. Difatti molti algoritmi si basano su delle serie di numeri mentre altri non li sanno trovare. Chiedo scusa.
Ogni naturale a > 1 è primo se e solo non è un quadrato e non è divisibile per alcun primo.
Leggevo di quanto i computer attuali sono in grado di svelare miliardi di numeri primi in pochi secondi. Quello però che omettono è che questi miliardi sono i primi tra i numeri più bassi. Per esempio da 1 a 30 miliardi ci sono circa un miliardo e trecento milia numeri primi. Ma quando questi si fanno più grandi la cosa diventa più complicata anche per i computer attuali. Sicuramente l'algoritmo che io ho postato non aumenta la velocità di ricerca, semplicemente la fa in modo diverso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo