Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* Numero primo
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
Daviz
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 31/01/06 16:02
Messaggi: 133

MessaggioInviato: 18 Mag 2006 20:24    Oggetto: Rispondi citando

ulisse ha scritto:
Franto ha scritto:
la soluzione geniale è creare un numero con cifre a caso tanto come fanno a controllare??? Very Happy Very Happy Very Happy


C'è un piccolo inconveniente: la funzione pi(n) che conta i numeri primi che precedono n e che asintoticamente si comporta come x/lnx dice che i numeri primi non sono poi così tanti.
Infatti un teorema dovuto a Legendre afferma che la probabilità che un numero n sia primo è 1/lnx che convertito a spanne nel logaritmo binario (logaritmo in base 2) sostanzialmente dice che la probabilità che n sia primo è inversamente proporzionale al numero di bit necessari a contenere la rappresentazione binaria di n.

Dunque la probabilità che un numero da 10 milioni di cifre decimali sia primo è nettamente inferiore a 1 su 10 milioni...

Se contempliamo la possibilità di "barare" sparando un numero che sembri primo ma in realtà non lo è ovvero un numero che superi i test di primalità senza essere primo (tali numeri vengono detti "pseudoprimi") scopriamo che non ci guadagniamo poi così tanto.
Infatti anche i numeri pseudoprimi sono veramente pochi.
Tanto per fare un esempio.
I numeri che soddisfano il piccolo teorema di Fermat (che fornisce una condizione necessaria per la primalità) senza essere primi (tali numeri sono detti numeri di Carmichael) sono ancora meno: tra i primi 10^9 interi ce ne sono solo 255!


Oddio Ulisse... più passa il tempo, e meno ti comprendo... E dire che a scuola andavo bene a matematica, e la sto ripassando per gli Alpha Test di Medicina. Very Happy

Alzi la mano chi ha capito... Shocked
Top
Profilo Invia messaggio privato
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 18 Mag 2006 20:59    Oggetto: Rispondi citando

Speak to the hand è la più simile ad una mano alzata...

Rischiando di mettere in gioco la tessera del club, devo dire che ho capito cosa ha detto Uli Saranno i due spritz, la birra e l'amaro che ho in circolo? pur non potendo ripeterlo con parole più semplici...
Top
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19146
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 18 Mag 2006 21:14    Oggetto: Rispondi citando

Speak to the hand

alzo la mano anch'io.
la maggioranza del club ha capito, ergo delibera di rimanere nel club.
a proprosito, strasimpa fa parte del club?
alb82, vuoi iscriverti anche tu (hai già tutti i requisiti necessari e sufficienti)?
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 18 Mag 2006 21:35    Oggetto: Rispondi citando

madvero ha scritto:
la maggioranza del club ha capito

Facile ottenere la maggioranza quando si è in quattro!
Strasimpa fa parte sicuramente del club, ma mi pare astenuto... quorum raggiunto e votazione valida... Wink
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 18 Mag 2006 23:14    Oggetto: Rispondi citando

alb82 ha scritto:
www.mersenne.org
Qua mi sembra di capire 2 o 3 cose un pochino diverse.
Stiamo parlando di numeri primi di Mersenne, non di numeri primi e basta.
Sono leggermente diversi, è scritto tutto sul sito.


Confermo. Il premio da 100,000 USD verrà attribuito a chi riuscirà a scovare un numero primo di Mersenne con almeno 10 milioni di cifre decimali.

I numeri primi di Mersenne sono dei particolari numeri primi. Ovvero sono numeri primi della forma 2^k-1.
Detto in maniera più pittoresca sono numeri primi la cui notazione binaria non contiene la cifra 0.
Non tutti i numeri 2^k-1 sono primi.
Ad esempio:
3=2^2-1 ha notazione binaria 11 ed è primo (e l'esponente k=2 è anch'esso primo)
7=2^3-1 ha notazione binaria 111 ed è primo (e k=3 è primo)
15=2^4-1 ha notazione binaria 1111 ma col cavolo che è primo (e nemmeno k=4 lo è)
31=2^5-1 ha notazione binaria 11111 ed è primo al pari di k che vale 5
63=2^6-1 indovinate un po'? k=6 non è primo e nemmeno 63 lo è
Qualcuno a questo punto ha congetturato che se k è primo anche 2^k-1 lo è.
Troppo bello per essere vero: prendi un primo p noto, calcoli 2^p-1 e hai un primo molto più grande che puoi usare come esponente per trovare un terzo primo mostruosamente più grande e così via all'infinito. Avremmo trovato un generatore di numeri primi. Troppo bello per essere vero.
Infatti è falso...

Ma torniamo ai primi di Mersenne.
Il 43° numero di Mersenne recentemente scovato è 2^30,402,457-1.
Come hanno fatto?
A meno di trucchetti a me ignoti il metodo è semplice.
Poiché non si conosce la distribuzione dei numeri di Mersenne (ovvero non si sa dove cavolo siano) non resta che scegliere un numero k a caso, calcolare n=2^k-1 e sottoporre n a un test di primalità.

L'unica cosa che si può fare per ottimizzare la ricerca è fidarsi delle congetture (vedi http://primes.utm.edu/notes/faq/NextMersenne.html) sull'ubicazione di tali numeri.

Poiché i numeri di Mersenne vengono scovati sostanzialmente a casaccio (una verifica sistematica è impensabile) non c'è alcuna certezza che i 43 numeri di Mersenne sinora individuati siano effettivamente gli unici.
Per averne certezza bisognerebbe verificare uno ad uno i 30 milioni e rotti numeri del tipo 2^k-1 che precedono M(43).

A parte ciò, si ipotizza che il prossimo numero di Mersenne possa trovarsi intorno a k=38,000,000 avendo, dunque, più di 11 milioni di cifre decimali.

Perché concentrarsi sui numeri di Mersenne? perché la probabilità che un numero n sia primo è più elevata se esso viene scelto a caso tra i numeri del tipo 2^k-1.

Perché la confusione tra numeri primi generici e numeri primi di Mersenne? perché il più grande numero primo sinora noto è proprio il 43° numero di Mersenne.
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19146
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 18 Mag 2006 23:28    Oggetto: Rispondi citando

Applause Applause Applause

stavo proprio cercando in giro queste spiegazioni.
sei stato perfetto, chiaro e comprensibile.
(e poi io con l'inglese non ho una gran dimestichezza)

io ricordavo anche una formula tipo [2^(2^n - 1)] - 1.
l'ho sognata?
e se non l'ho sognata, ha attinenza?
Top
Profilo Invia messaggio privato Invia e-mail HomePage
alb82
Mortale pio
Mortale pio


Registrato: 18/05/06 09:36
Messaggi: 27

MessaggioInviato: 18 Mag 2006 23:47    Oggetto: Rispondi citando

Citazione:
alzo la mano anch'io.
la maggioranza del club ha capito, ergo delibera di rimanere nel club.
a proprosito, strasimpa fa parte del club?
alb82, vuoi iscriverti anche tu (hai già tutti i requisiti necessari e sufficienti)?

Ci vuole la tessera per iscriversi? Ah, perchè se non ci vuole allora non mi interessa Very Happy
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 18 Mag 2006 23:52    Oggetto: Rispondi citando

madvero ha scritto:
Applause Applause Applause

stavo proprio cercando in giro queste spiegazioni.
sei stato perfetto, chiaro e comprensibile.
(e poi io con l'inglese non ho una gran dimestichezza)

io ricordavo anche una formula tipo [2^(2^n - 1)] - 1.
l'ho sognata?
e se non l'ho sognata, ha attinenza?


Non l'hai sognata. E' quello che dicevo prima sulla congettura, purtroppo falsa, che se p è primo anche 2^p-1 lo è.
Se fosse vera allora si parte con un qualsiasi primo p(0).
Si calcola p(1)=2^p(0)-1 che, se la congettura fosse vera, sarebbe anch'esso certamente primo.
Allora p(2)=2^p(1)-1=2^[2^p(0)-1]-1 sarebbe anch'esso primo.
E così via...
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 19 Mag 2006 00:02    Oggetto: Rispondi citando

alb82 ha scritto:
Ci vuole la tessera per iscriversi? Ah, perchè se non ci vuole allora non mi interessa Very Happy


Non so perché ma questa cosa mi ricorda tanto una singolare "barriera" comparsa parecchi anni or sono in calce ai moduli per la presentazione del piano di studi per la laurea in matematica:

Citazione:
Propedeuticità: per iscriversi all'esame di Analisi Matematica I è necessario aver già sostenuto l'esame di Analisi Matematica I

Shocked Shocked Shocked
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19146
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 19 Mag 2006 00:06    Oggetto: Rispondi

alb82 ha scritto:
Ci vuole la tessera per iscriversi? Ah, perchè se non ci vuole allora non mi interessa Very Happy

vabbè, se ci tieni, fai tu le tesserine per tutti (noi non le abbiamo). Wink
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a Precedente  1, 2, 3, 4, 5, 6  Successivo
Pagina 3 di 6

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi