Prime is in P

tmart · Messaggio da **tmart** » 01 gen 1970, 01:33

Volevo chiedervi una dimostrazione:
 
 perché 2^n+1 con n=0 o n=2^x con 0<=x<=4 forma un numero primo mentre con x>=5 ciò non avviene più?
 
 con i primi di Mersenne (2^p-1) sto cercando di dare un dimostrazione basata sulle serie, dato che (2^p-1)/(2-1)=2^(p-1)+2^(p-2)+...+2^2+2^1+2^0
 
 ovvero è una serie di 111111...
 Infatti rappresentando in codice binario i numeri primi uno sotto l\'altro vengono fuori dei disegni con incredibili corrispondenze; se qualche appassionato vuol provare, gli consiglio di scriversi in C una funzione che assegna allo 0 un quadrato vuoto e all\'1 un quadrato pieno.
 Classica nei numeri primi di Mersenne (ovvero nelle potenze di due -1) è la ripetizione dei 7, ancora non sono riuscito a trovare la frequenza esponenziale in 2^13466917-1.
 
 Con questo chiudo perché ho già passato 2:06 ad analizzare le serie e i numeri primi e decido su due piedi di smettere e di lasciare il compito alla CIA e agli assatanati dei numeri primi (ricordo: se qualcuno di voi trova un numero primo con 10.000.000 di cifre in base decimale il premio è di 100.000 $, che possono sempre far comodo)io non riesco a CREDERE nei numeri primi, anche se abbracciarne fisicamente e mentalmente uno con 4 milioni di cifre mi ha fatto credere in un certo senso di abbracciare il Sasso Lungo (Dolomiti...) . <IMG SRC="images/forum/icons/icon_confused.gif">
 
 <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_eek.gif">
 
 Sì forse stanotte era meglio dormire piuttosto che scomporre in fattori primi 2^65526+1 e scoprire che la mia serie era un fallimento iperbolico!
 
 A questo punto se qualcuno vuole discutere sulle potenzialità dell\'algoritmo di Manindra... Io lo sto decifrando, appena ho finito vi fo un fischio.
 
 [addsig]

ReKaio · Messaggio da **ReKaio** » 01 gen 1970, 01:33

esistono algoritmi molto più veloci per testare i primi di mersenne, cerca \"lucas-lehmer\"\" su google, c\'è parecchio anche in italiano

publiosulpicio · Messaggio da **publiosulpicio** » 01 gen 1970, 01:33

www.mersenne.org (c\'è anche una sezione in italiano) e trovi un bel po\' di teoria sui primi di mersenne

tmart · Messaggio da **tmart** » 01 gen 1970, 01:33

Vi ringrazio per il materiale che mi dimostra quanto sia inutile cimentarsi sui numeri primi con gli interessi economici che ci sono... un povero studente è meglio che si dedichi a qualcos\'altro!
 
 eh eh.---

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

Ti dirò: le parole con cui rassegni la tua resa mi lasciano alquanto perplesso sulla vera natura della tua vocazione alla Matematica! Anch\'io non sono altri che un povero studente, come pateticamente hai scelto TU di definirti, eppure continuo a dedicarmi agli studi Matematici con la stessa passione di ieri, giungendo persino a mettere in subordine la mia pur onorata carriera universitaria! Forse questo mio bel discorso, di tanta retorica farcito, ti sembrerà antico e presuntuoso, ma almeno è coerente... come del resto è obbligo che sia, mi permetto di replicare, dacché qui si sta parlando di Matematica, non già di calcio o di politica... convincitene e nulla ti apparirà impossibile! <IMG SRC="images/forum/icons/icon_wink.gif">

Antimateria · Messaggio da **Antimateria** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-02 10:07, tmart wrote:
 Volevo chiedervi una dimostrazione:
 perché 2^n+1 con n=0 o n=2^x con 0<=x<=4 forma un numero primo mentre con x>=5 ciò non avviene più?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 In realtà non è proprio così. Un numero della forma 22n+1 si dice numero di Fermat, e la congettura che ogni numero di Fermat è primo è stata formulata da Fermat, e confutata da Eulero un secolo dopo! Il problema di trovare un numero di Fermat primo con n>4 è aperto, ma si pensa che tali numeri siano infiniti. Qualcuno ha congetturato allora che i numeri di Fermat della forma 222n+1 fossero tutti primi, ma anche questo è falso, perchè 2216+1 è composto.

Barozz · Messaggio da **Barozz** » 01 gen 1970, 01:33

penso che 2^n+1 con 0<=x<=4 è solo una generalizzazione delle formule:
 
 4^n+1 e 4^n-1 che sono numeri primi!

Messaggio da **FrancescoVeneziano** » 01 gen 1970, 01:33

Una correzione a quanto detto da Antimateria: si congettura che i primi di Fermat siano finiti, e anzi che siano solo quelli conosciuti da Fermat; l\'Hardy-Wright riporta anche un argomento empirico a favore di questa ipotesi basato su considerazioni di \"probabilità\" non rigorose.
 
 CaO (ossido di calcio)

Messaggio da **FrancescoVeneziano** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-06 11:02, Barozz wrote:
 penso che 2^n+1 con 0<=x<=4 è solo una generalizzazione delle formule:
 
 4^n+1 e 4^n-1 che sono numeri primi!
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Non so cosa intendessi con queste parole, ma 4^n-1 è sempre multiplo di 3, mentre 4^3+1=5*13
 
 CaO (ossido di calcio)

Antimateria · Messaggio da **Antimateria** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-06 11:09, FrancescoVeneziano wrote:
 Una correzione a quanto detto da Antimateria: si congettura che i primi di Fermat siano finiti, e anzi che siano solo quelli conosciuti da Fermat; l\'Hardy-Wright riporta anche un argomento empirico a favore di questa ipotesi basato su considerazioni di \"probabilità\" non rigorose.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ok, buono a sapersi, avevo letto su Wolfram quest\'altra cosa:
 \"Eisenstein (1844) proposed as a problem the proof that there are an infinite number of Fermat primes.\".

genovese · Messaggio da **genovese** » 01 gen 1970, 01:33

Oltre a ribadire l\'argomento di Francesco sul fatto che i numeri primi di Fermat sono molto probabilmente finiti e in realtà sono quelli già noti (anche se una dimostrazione di ciò mi sembra abbastanza improbabile) vorrei aggiungere alcune informazioni per i curiosi.
 Innanzitutto Fermat aveva congetturato che tali numeri fossero tutti primi. Aveva inoltre anche dimostrato che un possibile fattore primo di 2^(2^n)+1 deve essere congruo a 1 modulo 2^(n+2). Tale teorema non è tanto difficile da dimostrare anche se richiede qualche conoscenza non liceale.
 
 Facciamo qualche esempio.Prendiamo 2^(2^4)+1. Per quanto detto un possibile fattore primo deve essere congruo a 1 modulo 2^6, ovvero deve essere della forma 64k+1. Ora 65 non è primo, 129 non è primo, 193 non divide 65537 e 257 è già più grande della radice di 65537 e quindi neanche lo provo. Ragionamenti analoghi si possono fare con primi di Fermat più piccoli.
 
 Ma vediamo cosa succede nel caso del quinto numero di Fermat, 2^(2^5)+1. Come abbiamo detto un possibile fattore deve essere congruo a 1 modulo 2^7, ovvero essere della forma 128k+1. Si vede allora che 129 non è primo, 257 non divide 4294967297, 385 non è primo, 513 non è primo e 641, guarda caso, divide 4294967297! Non abbiamo dovuto fare calcoli astronomici. Come ha fatto Fermat a non accorgersene? Non si sa.
 
 Tali ragionamenti dovrebbero convincervi che la primalità dei piccoli numeri di Fermat dipende dal fatto che ci sono delle restrizioni sui primi che li possono dividere ma quando prendiamo numeri di Fermat molto grandi tali restrizioni non sono più così vincolanti e quindi la probabilità che tali numeri siano primi si avvicina a quella di numeri presi a caso delle stesse dimensioni. E visto quanto crescono i numeri di Fermat questa diventa piccola molto velocemente.
 
 Ragionamenti analoghi si possono fare con i numeri di Mersenne, ovvero i famosi 2^p-1. Esiste un teorema analogo che afferma che i fattori primi devono essere congrui a 1 modulo 2p. Guarda caso 2^11-1=23*89 si scompone molto facilemente con questo criterio. La crescita più lenta dei numeri di Mersenne fa sì che se ne siano trovati parecchi primi e forse che questi siano addirittura infiniti (anche questa affermazione può trovare solo basi empiriche).
 
 La bellezza di tali numeri risiede nel fatto che esistono algoritmi molto semplici per verificare la loro primalità e tale semplicità ne fa degli ottimi candidati per la ricerca di numeri primi molto grandi. Guardate il sito <a href="http://www.mersenne.org/prime.htm" target="_blank" target="_new">http://www.mersenne.org/prime.htm</a> se siete curiosi.
 
 Spero di essere stato chiaro <IMG SRC="images/forum/icons/icon_wink.gif">

tmart · Messaggio da **tmart** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-05 23:22, euler_25 wrote:
 Ti dirò: le parole con cui rassegni la tua resa mi lasciano alquanto perplesso sulla vera natura della tua vocazione alla Matematica! Anch\'io non sono altri che un povero studente, come pateticamente hai scelto TU di definirti, eppure continuo a dedicarmi agli studi Matematici con la stessa passione di ieri, giungendo persino a mettere in subordine la mia pur onorata carriera universitaria! Forse questo mio bel discorso, di tanta retorica farcito, ti sembrerà antico e presuntuoso, ma almeno è coerente... come del resto è obbligo che sia, mi permetto di replicare, dacché qui si sta parlando di Matematica, non già di calcio o di politica... convincitene e nulla ti apparirà impossibile! <IMG SRC="images/forum/icons/icon_wink.gif">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ehi, Euler25... Mi riferivo solo ai numeri primi e comunque... Se non fossi interessato alla Matematica non cercherei di ridimostrare cose che già hanno dimostrato (senza che io sappia che lo hanno fatto) per \"farmi il callo\" ...
 
 Comunque intendevo dire che mi interessano più altri campi della Matematica (non ricevo il giusto stimolo dai numeri primi per poter lavorare giorni su di essi)...
 
 buhbye![addsig]

tmart · Messaggio da **tmart** » 01 gen 1970, 01:33

Anche se più ci ripenso e più mi viene voglia di scoprire... Soprattutto avendo appena compreso Manindra!!! Evviva! Non ci sono limiti per l\'uomo, poiché lui li inventa...
 
 Con questo chiudo questo reparto del Forum UFFICIALMENTE, quindi potete continuare a postare <IMG SRC="images/forum/icons/icon_wink.gif">

germania2002 · Messaggio da **germania2002** » 01 gen 1970, 01:33

l\'uomo che fà?
 inventa, quando? mai inventata una cosa senza prendere spunto dalla natura, che per me, sia ben chiaro non sarà mai superata.
 Anche tutti i film sulle macchine intelligenti etc..... pensandoci un pò sono partito col mio solito ragionamento sballato:
 Ipotesi:
 A: la natura seleziona solo gli organismi che si adattano di più ai problemi ambientali e sociali per sopravvivere
 B: la natura tende a creare e selezionare organismi che sono robusti,intelligenti e richiedono poca energia, quindi tende ad essere molto efficente.
 C: un\'organismo non efficente viene distrutto.
 D: di solito l\'evoluzione di una specie tende sempre al meglio, quindi non può essere (nel complesso) sbagliata totalmente.
 E: la matematica è immanente all\'universo
 
 poichè gli organismi scelti dalla natura sono organismi composti da molecole organiche, le macchine pensanti dalle ipotesi B,C,D si deduce che non potranno mai esistere organismi autonomi fatti solo da materiali inorganici, al massimo potranno emulare un\'intelligenza poichè sono strutturati in un modo che ricalca la logica (E) di un\'intelligenza, ma senza mai essere veramente autonomi. Poi il discorso è lungo, se volete spiegato il mio ragionamento ve lo dico, s enò non fà niente.
 
 PS: naturalmente le mie sono ipotesi elaborate grazie agli spunti presi su vari libri e dall\'esperienza personale, non sò se sono vere e non le voglio imporre a nessuno.[addsig]

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

Germania, 6 eccezionale!!! E non aggiungo altro... <IMG SRC="images/forum/icons/icon_wink.gif">