C'è un algoritmo che genera numeri primi?
Arcobaleno
primo come il più grande possibile ?
news.tin.it
> Se c'è basta usare l'induzione e quindi definire l'ennesimo numero
> primo come il più grande possibile ?
c'è un algoritmo ed è anche molto semplice:
http://armellini.pbworks.com/f/crivello.pdf
trovi il codice in Python e in PARI/GP
http://www.box.net/shared/kztlf24yda
mentre con questo programma in Java puoi costruire liste di primi grandi
a piacere a partire da qualunque intervallo con bassa probabilità di errore
----------------------------------------
package primi2;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.*;
public class Main {
public static void main(String[] args) {
long j =1;
BigInteger inizio = new BigInteger("3");
BigInteger passo = new BigInteger("2");
inizio = inizio.add(passo);
System.out.println(inizio);
while(j < 100000){
if( inizio.isProbablePrime(100000000))
System.out.println(inizio);
inizio = inizio.add(passo);
j = j+1;
}
j = j+1;
inizio = inizio.add(passo); }
}
----------------------------------------------
altri sistemi li trovi (vairanti del crivello di eratostene):
http://armellini.pbworks.com/f/crivello-primi.rar
radiazione di fondo
> > primo come il pi grande possibile ?
Non capisco bene la domanda. Comunque ci sono svariati algoritmi per
generare numeri primi.
Da un punto di vista matematico (quindi senza pensare all'efficienza)
un numero p e' primo se e solo se (p-1)!+1 e' un multiplo di p
(teorema di Wilson)
anche se a nessuno verrebbe in mente di usare questo sistema in
pratica.
> c' un algoritmo ed anche molto semplice:http://armellini.pbworks.com/f/crivello.pdf
Questo e' un algoritmo molto inefficiente.
In pratica per determinare se un numero x e' primo fai il minimo
comune multiplo
tra x e il prodotto di tutti i primi precedenti piu' piccoli di
sqrt(x).
> altri sistemi li trovi (vairanti del crivello di eratostene):
> http://armellini.pbworks.com/f/listadeiprimi.pdf
Ho guardato il programma. Contiene diversi errori e quindi non
compila.
A parte gli errori, usi fmod() che e' una funzione su numeri in
floating point
per fare il modulo tra due interi. Per il modulo tra due interi x e y
basta fare x % y.
Inoltre il programma potrebbe essere molto migliorato, pur rimanendo
estremamente elementare. Per esempio, il vettore di long lista[k] e'
sottoutilizzato
in quanto viene usato come indicatore binario del fatto che k sia
primo
o meno e non viene riempito come normalmente si fa con il crivello di
Eratostene,
ma per ogni dispari vai a vedere comunque se e' primo o no dividendolo
per
tutti i dispari minori della sua radice. A questo punto, tanto vale
sfruttare il
vettore lista[] per memorizzare i primi trovati fino a quel momento, e
quindi
dividere non per tutti i dispari, ma solo per i primi.
Per un crivello piu' efficiente di quello di Eratostene e una sua
implementazione
molto ottimizzata, puoi guardare qui e nel link in fondo alla pagina:
http://en.wikipedia.org/wiki/Sieve_of_Atkin
radiazione
Arcobaleno
>
>
> Non capisco bene la domanda. Comunque ci sono svariati algoritmi per
> generare numeri primi.
>
Grazie, sei davvero molto gentile!
L'algoritmo che servirebbe dovrebbe poter GENERARE tutti i numeri
primi.
Per es noi sappiamo estrarre una radice quadrata di un numero intero
qualsiasi.
Questo è un algoritmo e cioè un procedimento.
Allo stesso modo ci vorrebbe un procedimento per poter generare per
induzione
QUALSIASI numero primo.
>
> Da un punto di vista matematico (quindi senza pensare all'efficienza)
> un numero p e' primo se e solo se (p-1)!+1 e' un multiplo di p
> (teorema di Wilson)
> anche se a nessuno verrebbe in mente di usare questo sistema in
> pratica.
>
Invece penso che vada benissimo:) Non lo conoscevo.
Possiamo quindi dire che TUTTI i multipli di (p - 1) ! + 1 per ogni p
t.c. p € N,
sono numeri primi e questo lo hai già detto tu e mi dici che è stato
dimostrato.
Ora per induzione bisognerebbe dimostrare che per ogni p_n (dove n =
ennesimo numero primo)
esiste un p_n+ 1.
Quello che si dovrebbe dimostrare(o quanto meno mettere in linguaggio
formale) è che ad ogni numero primo
segue un altro numero primo che sia o non sia il successore naturale.
Si tratta cioè di avere una sorta di "sicurezza" che per p(p = numero
primo) grande a piacere
esiste un p maggiore.
Per es noi siamo sicuri che dopo 7 c'è 11 e dopo ancora 13 ecc e
neppure lo andiamo a dimostrare...
Quindi il primo passaggio è quello di dimostrare che PER OGNI p grande
a piacere c'è un p maggiore.
Poi magari un altro passaggio per dimostrare che il numero primo più
grande da poter immaginare
è tale anche se TENDE(infinito potenziale) ad infinito.
A cosa mi serve questo ragionamento?
Mi serve per considerare la possibilità che pur non potendo noi dire
qual è il numero naturale più grande
e inoltre neppure possiamo dire che è un numero INFINITO in atto, però
possiamo dire che un numero primo
potendo essere DIVISO SOLO per se stesso ecco che avrà una
particolarissima proprietà.
CIoè p_inf / p _inf = 1.
Però per poter dire una cosa del genere devo poter asserire che un
numero primo INFINITO esiste.
Ovviamente per non avere i soliti imbarazzi logici parleremo di p_n
per n che TENDE a infinito.
Quindi il Lim di p_n / p_n è 1 quando n tende a infinito.
Voglio capire con questo genere di ragionamento anche se riusciamo a
FORZARE un po' sulle convenzioni o siamo rimasti fermi all'ipse dixit
dei grandi del passato e quindi non ci concediamo un po' di arbitrio.
Se Cantor si mise a parlare di infinito in atto non vedo perché noi
non potremmp "giocare" con l'infinito potenziale:)
Geppo
> Se c'è basta usare l'induzione e quindi definire l'ennesimo numero
> primo come il più grande possibile ?
scusa, magari non ho capito cosa intendi, ma anche ponendo
di avere una funzione f:N ->N che genera solo numeri primi
cosa c'entra il principio di induzione per dire che esiste
un primo piu' grande? Anzi, la stessa esistenza della f(n)
di cui sopra sarebbe una ulteriore conferma al fatto che i
primi sono infiniti. ciao :)
Arcobaleno
ma visto che questa funzione non esiste ecco che operiamo su di una
formula(tipo quella
che hai scritto tu) ragionando in termini induttivi(come ho
velocemente accennato) e così
possiamo dire che dopo OGNI primo grande a piacere c'è un altro primo
maggiore.
Per me(ma penso anche per altri) non è scontato il fatto che andando
ad infinito debba per forza
esistere un numero primo.
Cioè non ho alcuna intuizione per poter dire che dopo un primo grande
a piacere sicuramente ci sarà
un altro primo.
Non posso andare a VERIFICARE sul SINGOLO numero primo grande a
piacere e poi su quello che segue.
Dovrei poi fare questo procedimento indefinitamente e lo stesso dire
"primo grande a piacere" non avrebbe senso.
Quello che mi permette di fare il ragionamento per induzione è andare
sul sicuro e cioè che ESISTE davvero quel primo grande a piacere e non
è solo un nostro dire.
Poi, inoltre, visto che usiamo il concetto di infinito potenziale noi
in realtà è come se dicesso: sciegliendoci un numero primo maggiore
del precedente e poi un altro ancora maggiore e ancora maggiore ecco
che troverai un altro ancora maggiore ecc ecc.
Ma poter parlare in questi termini di infinito potenziale è possibile
se davvero ci sono questi INFINITI numeri primi.
Nel caso dei naturali infiniti noi capiamo che che ce ne sono di
infiniti perché applichiamo per ogni n n+1 e siccome sappiamo che è
possibile SOMMARE ad ogni n in numero uno ecco che ne deduciamo che
esiste un SUCCESSORE.
Ma per i primi siccome non abbiamo l'algoritmo ecco che ci dobbiamo
arrangiare(si fa per dire) con un procedimento induttivo.
A meno che non vi sia davvero un algoritmo che li generi. Ma anche in
quel caso il ragionamento per induzione bisogna ESPLICITARLO...per i
NATURALI questo ragionamento è sottointeso e però come vedi qui sopra
l'ho esplicitato. Nel caso dei primi va esplicitato il procedimento
induttivo.
Ed ecco che possiamo dire che il limite del RAPPORTO tra due primi
UGUALI dove il numero primo a cui pensiamo tende ad essere il maggiore
di ogni primo è UNO.
Allo stesso modo possiamo dire per i naturali e cioè che il limite del
rapporto tra due naturali uguali al tendere di questo naturale ad
infinito è UNO.
Il procedimento di induzione ci serve per poter agire su di una
formula affinché la stessa ci assicuri che procedendo indefinitamente
la stessa sia valida.
Nel caso della formula che hai scritto tu questa induzione è data
dalla DIMOSTRAZIONE di Wilson.
Ed è questa dimostrazione che sottointende l'uso di un ragionamento
induttivo perché avrà PROVATO che PER OGNI p vale quella formula.
Quello che ho aggiunto questa mattina è l'avere detto che i due numeri
del rapporto m/n sono uguali e cioè m = n.
Infinito diviso infinito fa UNO se i due numeri sono uguali:))
A scuola se non ricordo male ci dicevano che infinito diviso infinito
è indeterminato. Giusto?
Geppo
> Per me(ma penso anche per altri) non è scontato il fatto che andando
> ad infinito debba per forza
> esistere un numero primo.
faccio un po' di fatica a seguirti ma sicuramente e' un limite mio :)
cosa intendi con "andando a infinito" ? Se intendi che, per ogni N
grande a piacere, esiste M primo tale che M > N, e' senz'altro vero,
dato che dimostriamo facilmente che i primi sono infiniti; se non
fosse vera, significherebbe che esiste un limite superiore ai numeri
primi e sarebbe una contraddizione.
> Nel caso dei naturali infiniti noi capiamo che che ce ne sono di
> infiniti perché applichiamo per ogni n n+1 e siccome sappiamo che è
> possibile SOMMARE ad ogni n in numero uno ecco che ne deduciamo che
> esiste un SUCCESSORE.
>
> Ma per i primi siccome non abbiamo l'algoritmo ecco che ci dobbiamo
> arrangiare(si fa per dire) con un procedimento induttivo.
non capisco a cosa vuoi arrivare ... il fatto di poter costruire gli
infiniti
elementi di un insieme prendendo un "precedente" e costruendo un
"successore" (cosa che si puo' fare con gli interi) non e' mica
condizione
necessaria per affermare che, appunto, l'insieme e' infinito: con i
reali
p.es. non e' possibile, e nemmeno con l'insieme delle funzioni
continue
tra [0,1] ...
>
> A meno che non vi sia davvero un algoritmo che li generi. Ma anche in
> quel caso il ragionamento per induzione bisogna ESPLICITARLO...per i
> NATURALI questo ragionamento è sottointeso e però come vedi qui sopra
> l'ho esplicitato. Nel caso dei primi va esplicitato il procedimento
> induttivo.
>
> Ed ecco che possiamo dire che il limite del RAPPORTO tra due primi
> UGUALI dove il numero primo a cui pensiamo tende ad essere il maggiore
> di ogni primo è UNO.
questo non lo capisco proprio, il rapporto tra due QUALSIASI numeri
uguali
e' 1 ...
>
> Allo stesso modo possiamo dire per i naturali e cioè che il limite del
> rapporto tra due naturali uguali al tendere di questo naturale ad
> infinito è UNO.
cioe' lim n->oo (n/n) = 1 ? ok ...
>
> Infinito diviso infinito fa UNO se i due numeri sono uguali:))
>
io ricordo che oo / oo non ha senso, ha senso invece quella di sopra
cioe' lim n->oo (n/n) = 1
> A scuola se non ricordo male ci dicevano che infinito diviso infinito
> è indeterminato. Giusto?
si ma credo sia una notazione imprecisa per dire che, moltiplicando
oo per qualsiasi numero si ha sempre oo ... comunque probabilmente
intendi qualcosa di piu' profondo che non ho colto, non importa,
grazie
della discussione comunque :) ciao.
radiazione di fondo
> Quello che si dovrebbe dimostrare(o quanto meno mettere in linguaggio
> formale) è che ad ogni numero primo
> segue un altro numero primo che sia o non sia il successore naturale.
Questo lo aveva gia' dimostrato Euclide (che esistono infiniti numeri
primi).
La dimostrazione per assurdo e' banale.
Supponiamo per assurdo che esistano solo un numero finito di numeri
primi,
da p_1 a p_k. Poniamo n uguale a 1 piu' il prodotto di tutti i numeri
primi esistenti.
Ora, i casi sono 2.
o n e' primo o n e' composto. Se n e' primo, siccome e' maggiore di
tutti
i primi p_1, ..., p_k, allora si contraddice l'ipotesi che p_k sia
l'ultimo primo.
viceversa, se n e' composto deve essere il prodotto di primi.
Tuttavia,
per costruzione, il resto della divisione di n per p1, o p2, o..., p_k
e' sempre
1, quindi non e' divisibile per i primi noti e quindi devono esserce
degli altri.
Anche il teorema o postulato di Bertrand che dice che tra un numero
n>1 e il suo
doppio 2n c'e' sempre un numero primo ci fa capire che sono infiniti.
radiazione
Tommaso Russo, Trieste
> teorema o postulato di Bertrand
Congettura di Bertrand o teorema di Chebyshev.
Postulato non puo' esserlo.
--
TRu-TS
Buon vento e cieli sereni
radiazione di fondo
wrote:
> On 15 Mar, 10:01, Geppo <marco.f1...@gmail.com> wrote:
> > scusa, magari non ho capito cosa intendi, ma anche ponendo
> > di avere una funzione f:N ->N che genera solo numeri primi
> ma visto che questa funzione non esiste
Certo che esiste una funzione f:N->N che genera solo i numeri primi.
Anzi e' esattamente la funzione p:N->N che ad ogni numero k assegna
il k-esimo numero primo. p(1)=2, p(2)=3, p(3)=5, p(4)=7, etc.
Per definirla bastano le operazioni aritmetiche, le parti intere
superiori e inferiori (floor e ceiliing),
e la sommatoria. Maggior dettagli :
http://it.wikipedia.org/wiki/Formula_per_i_numeri_primi
Naturalmente queste definizioni in forma di funzione sono sono
efficienti
da un punto di vista computazionale.
radiazione
Tommaso Russo, Trieste
> On Mar 15, 9:44 pm, "Tommaso Russo, Trieste"<tru...@tin.it> wrote:
>> Postulato non puo' esserlo.
>
> Mi ero mangiato un Chebyshev...
> Comunque a volte lo chiamano anche Bertrand's postulate.
> (non dico che sia corretto, ma lo chiamano cosi'...)
Ah, beh, loro possono postulare quello che vogliono, ma io non lo
concedo ;-)
Al massimo posso accettarlo come congettura da dimostrare, e tutti i
teoremi basati su di essa sono subordinati alla sua eventuale
dimostrazione (che nel caso particolare alla fine e' arrivata a opera di
Chebyshev).
> radiazione
Ti sei tradito... :-)
Giovanni Resta
Si, a volte passando da un computer all'altro, da un newsreader
all'altro, da un account gmail creato temporaneamente all'altro,
da una virtualbox all'altra, non ricordo piu' bene sotto quale nome
sto scrivendo.
In passato sono stato o credo di essere stato
anche Caro Estintore, Vanvera, Nano Bagonghi... ma e' una cosa fatta
senza malizia, piu' che altro per pigrizia (di uniformare i vari nick):
non e' che con un nick mi faccio una domanda e con l'altro mi rispondo...
g./rad.d.f./c.e./n.b./v.....
superpollo
>> radiazione
>
> Ti sei tradito... :-)
morfone!
--
La Tunze non ha bisogno di voi, perchè e' logica pura.
Siete Voi che avete bisogno della Tunze, per non perdere
il rispetto dei posteri.
Arcobaleno
>
>
> Ah, beh, loro possono postulare quello che vogliono, ma io non lo
> concedo ;-)
>
> Al massimo posso accettarlo come congettura da dimostrare, e tutti i
> teoremi basati su di essa sono subordinati alla sua eventuale
> dimostrazione (che nel caso particolare alla fine e' arrivata a opera di
> Chebyshev).
>
Quindi quello di Euclide tu non lo accetti?
Mi spieghi quello di Chebyshev invece?
Anche io faccio fatica ad accettare quelle che sono delle congetture
perché NON tutte le implicazioni del ragionamento sono evidenti.
Arcobaleno
>
> In passato sono stato o credo di essere stato
> anche Caro Estintore, Vanvera, Nano Bagonghi... ma e' una cosa fatta
> senza malizia, piu' che altro per pigrizia (di uniformare i vari nick):
> non e' che con un nick mi faccio una domanda e con l'altro mi rispondo...
>
Tanto lo so bene che siamo in pochi:))
Ed è questo il vero problema e cioè quando il numero dei nick supera
le
persone che li usano.
Di me si potrà dire tanto male ma sull'identità ci ho tenuto sempre
molto...
La penso un po' come Tommaso su quelle dimostrazioni.
Ed è sulle dimostrazioni che sto provando a concentrarmi.
Penso che si faccia spesso uso del principio di induzione anche quando
l'algoritmo
a disposizione non lo permetterebbe: come nel caso dei numeri primi.