UNA CONGETTURA SUI NUMERI PRIMI
Una delle tante concetture sui numeri primi è questa:
Non esiste nessun algoritmo, che preveda le sole operazioni che elencherò più sotto, che consenta di risolvere i seguenti problemi sui numeri primi. Ecco i problemi:
*dato un numero non è possibile trovare il primo immediatamente superiore o inferiore;
*dati due numeri non è possibile conoscere il numero di primi esistenti fra di loro e, di conseguenza, quali sono tali primi;
*dato un numero stabilire se è o no primo.
Ecco invece le caratteristiche degli algoritmi usabili ma che, se è vera la concettura, non risolverebbero i problemi suddetti:
*le quattro operazioni aritmetiche più la elevazione di potenza con esponente razionale;
*logaritmi con base razionale;
Non possono essere adoperati algortmi, diversi da quelli menzionati, basati sui tentativi né algoritmi che non abbiano un ciclo operativo di lunghezza predefinita e indipendente dal valore dei primi da determinare o dal numero di essi esistenti in un intervallo di ricerca.
mario1
Non esiste nessun algoritmo, che preveda le sole operazioni che elencherò più sotto, che consenta di risolvere i seguenti problemi sui numeri primi. Ecco i problemi:
*dato un numero non è possibile trovare il primo immediatamente superiore o inferiore;
*dati due numeri non è possibile conoscere il numero di primi esistenti fra di loro e, di conseguenza, quali sono tali primi;
*dato un numero stabilire se è o no primo.
Ecco invece le caratteristiche degli algoritmi usabili ma che, se è vera la concettura, non risolverebbero i problemi suddetti:
*le quattro operazioni aritmetiche più la elevazione di potenza con esponente razionale;
*logaritmi con base razionale;
Non possono essere adoperati algortmi, diversi da quelli menzionati, basati sui tentativi né algoritmi che non abbiano un ciclo operativo di lunghezza predefinita e indipendente dal valore dei primi da determinare o dal numero di essi esistenti in un intervallo di ricerca.
mario1
Risposte
Piacere Paola. Potrebbero anche usare il crivello di Eratostene puro, tanto mi sa che il costo non cambia. Quello che fanno e' collegare e far lavorare moltissimi computer allo stesso tempo.
Comunque, come ho gia' avuto modo di dire, la scoperta di un nuovo numero primo non e' un risultato matematico profondo; e' molto piu' profondo il Teorema di Euclide, che afferma che i numeri primi sono infiniti. Scoprire nuovi numeri primi non aiuta la teoria dei numeri.
Luca.
Comunque, come ho gia' avuto modo di dire, la scoperta di un nuovo numero primo non e' un risultato matematico profondo; e' molto piu' profondo il Teorema di Euclide, che afferma che i numeri primi sono infiniti. Scoprire nuovi numeri primi non aiuta la teoria dei numeri.
Luca.
Scusate, non mi sono firmata. ^_^ Sono Paola, piacere.
Per trovare numeri primi oggi, dato che sono arrivati a numeri di oltre 7 milioni di cifre, come fanno?
Ad esempio... Sul sito www.mersenne.org ne hanno trovato uno (non vorrei dire baggianate ma credo sia il più grande per ora) con il metodo di Mersenne per l'appunto... In un caso come questo avranno poi dovuto verificare un sacco di volte...
O usano algoritmi legati al crivello di Eratostene?
[Adoro la Teoria dei Numeri ^_-]
Ad esempio... Sul sito www.mersenne.org ne hanno trovato uno (non vorrei dire baggianate ma credo sia il più grande per ora) con il metodo di Mersenne per l'appunto... In un caso come questo avranno poi dovuto verificare un sacco di volte...
O usano algoritmi legati al crivello di Eratostene?
[Adoro la Teoria dei Numeri ^_-]
Il problema, cara prime number, e' che se i numeri sono enormi, algoritmi che usano criteri come il Teorema di Wilson sono, nel linguaggio dell'Analisi numerica, computazionalmente troppo costosi, ed hanno tempi troppo lunghi.
Luca.
Luca.
quote:
Originally posted by mariodic
*dato un numero stabilire se è o no primo.
mario1
Ma... partendo dal fatto che io non sono un'esperta, sto finendo le superiori, e la mia è solo passione, vorrei chiedere: ma non esiste il Teorema di Wilson nell'ambito delle congruenze che stabilisce se p è primo o no? [:I]
[:)] ciao a tutti
Tutto in realta' si puo' riassumere dicendo che non e' nota la distribuzione dei numeri primi in N. Purtroppo e' un problema molto difficile, ed e' antico quanto l'uomo; ha resistito a tutti i piu' grandi matematici: ma la Storia sta solo aspettando quella persona che riuscira' a determinare tale legge di distribuzione, per rendere immortale il suo nome.
Luca.
Luca.
Una correzione grammaticale: la parola "concettura" non esiste in italiano, ma congettura si.
Ciao, Ermanno
Ciao, Ermanno
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo