Prime is in P

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da tmart » 01 gen 1970, 01:33

Volevo chiedervi una dimostrazione:
<BR>
<BR>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ù?
<BR>
<BR>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
<BR>
<BR>ovvero è una serie di 111111...
<BR>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.
<BR>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.
<BR>
<BR>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">
<BR>
<BR> <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">
<BR>
<BR>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!
<BR>
<BR>A questo punto se qualcuno vuole discutere sulle potenzialità dell\'algoritmo di Manindra... Io lo sto decifrando, appena ho finito vi fo un fischio.
<BR>
<BR>[addsig]
[tex]\Im^\heartsuit_\TeX[/tex]

ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

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
_k_

publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

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
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

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!
<BR>
<BR>eh eh.---
[tex]\Im^\heartsuit_\TeX[/tex]

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

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">
<center>Le cose cambiano... e i sentimenti pure...</center>

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-12-02 10:07, tmart wrote:
<BR>Volevo chiedervi una dimostrazione:
<BR>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ù?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>In realtà non è proprio così. Un numero della forma 2<sup>2<sup>n</sup></sup>+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 2<sup>2<sup>2<sup>n</sup></sup></sup>+1 fossero tutti primi, ma anche questo è falso, perchè 2<sup>2<sup>16</sup></sup>+1 è composto.

Barozz
Messaggi: 123
Iscritto il: 01 gen 1970, 01:00
Località: Turbigo MI

Messaggio da Barozz » 01 gen 1970, 01:33

penso che 2^n+1 con 0<=x<=4 è solo una generalizzazione delle formule:
<BR>
<BR>4^n+1 e 4^n-1 che sono numeri primi!
I limiti sono fatti per essere risolti.

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

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.
<BR>
<BR>CaO (ossido di calcio)
Wir müssen wissen. Wir werden wissen.

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Messaggio da FrancescoVeneziano » 01 gen 1970, 01:33

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

Avatar utente
Antimateria
Messaggi: 651
Iscritto il: 01 gen 1970, 01:00
Località: Vergate sul Membro

Messaggio da Antimateria » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-12-06 11:09, FrancescoVeneziano wrote:
<BR>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.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ok, buono a sapersi, avevo letto su Wolfram quest\'altra cosa:
<BR>\"Eisenstein (1844) proposed as a problem the proof that there are an infinite number of Fermat primes.\".

genovese
Messaggi: 2
Iscritto il: 01 gen 1970, 01:00
Località: Lungarno Pacinotti, 51, PISA, 56100

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.
<BR>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.
<BR>
<BR>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.
<BR>
<BR>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.
<BR>
<BR>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.
<BR>
<BR>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).
<BR>
<BR>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.
<BR>
<BR>Spero di essere stato chiaro <IMG SRC="images/forum/icons/icon_wink.gif">

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da tmart » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2003-12-05 23:22, euler_25 wrote:
<BR>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">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>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\" ...
<BR>
<BR>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)...
<BR>
<BR>buhbye![addsig]
[tex]\Im^\heartsuit_\TeX[/tex]

tmart
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00
Contatta:

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...
<BR>
<BR>Con questo chiudo questo reparto del Forum UFFICIALMENTE, quindi potete continuare a postare <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>
[tex]\Im^\heartsuit_\TeX[/tex]

germania2002
Messaggi: 821
Iscritto il: 01 gen 1970, 01:00
Località: Cosenza
Contatta:

Messaggio da germania2002 » 01 gen 1970, 01:33

l\'uomo che fà?
<BR>inventa, quando? mai inventata una cosa senza prendere spunto dalla natura, che per me, sia ben chiaro non sarà mai superata.
<BR>Anche tutti i film sulle macchine intelligenti etc..... pensandoci un pò sono partito col mio solito ragionamento sballato:
<BR>Ipotesi:
<BR>A: la natura seleziona solo gli organismi che si adattano di più ai problemi ambientali e sociali per sopravvivere
<BR>B: la natura tende a creare e selezionare organismi che sono robusti,intelligenti e richiedono poca energia, quindi tende ad essere molto efficente.
<BR>C: un\'organismo non efficente viene distrutto.
<BR>D: di solito l\'evoluzione di una specie tende sempre al meglio, quindi non può essere (nel complesso) sbagliata totalmente.
<BR>E: la matematica è immanente all\'universo
<BR>
<BR>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.
<BR>
<BR>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]
"un uomo deve migliorare di qualcosa il mondo, se si vuole sentire realizzato..."
"Deutschland der beste Staat!"
[url:pvcj9bic]http://www.grid.org[/url:pvcj9bic] (pc vs cancro,sars,peste)

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

Germania, 6 eccezionale!!! E non aggiungo altro... <IMG SRC="images/forum/icons/icon_wink.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>

Bloccato