Numeri Primi [Archivio] - Hardware Upgrade Forum

dupa

18-12-2004, 02:31

Qualcuno mi sa dire se è mai stata trovata la percentuale di numeri primi esistenti rispetto all'infinità di numeri naturali?

Cioè pescando un numero a caso da 2 a +INF, qual'è la possibilità % che sia primo o che non lo sia...

grazie

jumpermax

18-12-2004, 03:49

Goldrake_xyz

18-12-2004, 09:45

Originariamente inviato da dupa
Qualcuno mi sa dire se è mai stata trovata la percentuale di numeri primi esistenti rispetto all'infinità di numeri naturali?

Cioè pescando un numero a caso da 2 a +INF, qual'è la possibilità % che sia primo o che non lo sia...

grazie

Purtoppo bisognerebbe trovare una formula in grado di
generare tutti i numeri primi possibili.
ma semra che questa formula non esiste, e quindi
i numeri primi vanno cercati per tentativi.
(intendo dire quelli molto grossi)
Forse c'è qualche formula empirica, o meglio di interpolazione,
che prevede la possibilità di trovare un numeroprimo dopo una
serie di N numeri..
:mc:

Lor3nzo76

18-12-2004, 10:17

La leggenda vuole che Riemann fosse riuscito a trovare un'ordine nella sequenza, ma i suoi scritti finirono bruciati quando l'esercito prussiano invase Gottinga...

Ciao
Lore

Banus

18-12-2004, 17:22

Originariamente inviato da jumpermax
una formula che approssima la frequenza credo sia n/ln(n) ma dipende dall'intervallo...
1/(n*log(n)) ;)

http://it.wikipedia.org/wiki/Teorema_dei_numeri_primi

Quindi la probabilità che un numero naturale preso a caso sia primo è 0 :p

dupa

18-12-2004, 17:41

Originariamente inviato da Banus
1/(n*log(n)) ;)

http://it.wikipedia.org/wiki/Teorema_dei_numeri_primi

Quindi la probabilità che un numero naturale preso a caso sia primo è 0 :p

il sito lì dice

prob = n / (LN n)

Banus

18-12-2004, 17:59

Originariamente inviato da dupa
il sito lì dice

prob = n / (LN n)
pi(x) del sito non è la probabilità ma il numero dei primi.
Infatti se aumenti n ottieni una probabilità maggiore di 1 che non ha senso.

La formula che ho scritto comunque è sbagliata :p
La probabilità di trovare un primo fra 0 e x è:

p(x) = pi(x)/x = 1/ln(x)

Ho confuso l'espressione asintotica del numero dei primi con quella del numero primo n-esimo :p
Ovviamente non è la probabilità esatta. La formula è un'approssimazione che vale per x molto alti.

ciriccio

19-12-2004, 08:26

Questo 3d me ne ricorda un altro...
Partimmo da qualche giochino che alcuni di noi avevano il piacere di inventarsi nei momenti "liberi" :asd: (gravi problemi personali... :asd: )e finimmo con una foto di Einstein e del poveretto che impazzì dopo aver scoperto che la matematica aveva in pratica dentro di se' qualcosa di 'indimostrabile :eek: :p

Chi se lo ricorda il 3d? Sulla congettura di Goldbach etc...

dupa

14-01-2005, 15:50

potrebbe essere inserito questo thread in rilievo per la matematica.. ciao :)

Ziosilvio

14-01-2005, 17:48

Originariamente inviato da dupa
pescando un numero a caso da 2 a +INF, qual'è la possibilità % che sia primo o che non lo sia...
Detta così, la cosa non ha molto senso.
In effetti, "pescare a caso" presuppone l'esistenza di una distribuzione di probabilità uniforme: ma su uno spazio infinito discreto non puo' esistere una d.d.p. uniforme (ESERCIZIO: dimostrare).

Ha senso, invece, dato un insieme S di interi positivi, e detto S[n] il numero degli elementi di S che non superano n, considerare lim inf e lim sup della quantità S[n]/n; se queste quantità coincidono, si può definire la densità di S (attenzione: densità, non probabilità) come il loro valore comune.
In questo caso, dato che, come già detto in questo thread, per l'insieme S dei numeri primi vale:
S[n] log n
lim ---------- = 1
n-->+oo n
si ha che la densità dell'insieme dei numeri primi è 0.

ChristinaAemiliana

14-01-2005, 21:03

http://forum.hwupgrade.it/showthread.php?s=&threadid=601451

Pensate, tempo fa avevo aperto questo!!!

Aggiungo il topic alla lista! :)

dupa

16-02-2005, 12:24

Scoperchiatore

17-02-2005, 12:55

Originariamente inviato da ciriccio
Questo 3d me ne ricorda un altro...
Partimmo da qualche giochino che alcuni di noi avevano il piacere di inventarsi nei momenti "liberi" :asd: (gravi problemi personali... :asd: )e finimmo con una foto di Einstein e del poveretto che impazzì dopo aver scoperto che la matematica aveva in pratica dentro di se' qualcosa di 'indimostrabile :eek: :p

Chi se lo ricorda il 3d? Sulla congettura di Goldbach etc...

Il poveretto è Godel, e la sua scoperta è definita da molti la rivoluzione più importante in matematica nel '900. :D

Solo che è ignoto, mentre Einstein lo conoscono tutti :mbe: Perchè?

Banus

17-02-2005, 13:18

Originariamente inviato da Scoperchiatore
Solo che è ignoto, mentre Einstein lo conoscono tutti :mbe: Perchè?
Godel ignoto? Non si contano le volte che viene citato... l'abbiamo pure visto in informatica teorica. Sono i suoi teoremi che sono bistrattati.. ad esempio pochi fanno notare che appena trovi qualcosa di indimostrabile, lo metti come assioma e buonanotte (le geometrie non euclidee insegnano :D).

damxxx

17-02-2005, 18:51

Originariamente inviato da dupa
che storia, ieri ho preso in biblioteca il libro "L'enigma dei numeri primi", e ho scoperto che anche gauss si era posto la stessa domanda :D

Son già arrivato a pagina 200!! il libro è una figata assurda, consiglio a tutti di leggerlo.

ciao

Anke io sto leggendo questo libro sn arrivato quasi alla fine,

la formula ke trovò Gauss serviva a dare una stima del numero di numeri primi inferiore a un dato numero N la formula era N/log(N), poi la xfezionò utilizzando il logaritmo integrale trasformandola in N/Li(N), qualcuno ha dimostrato ke l'errore della stima dei numeri primi fatta cn questa formula nn è mai maggiore dell'11%.
Riemann sembra sia riuscito a trovare una formula in grado di darc il numero esatto dei numeri primi inferiori a N, sembra xò ke la dimostrazione d tale formula sia andata xduta, ed ora questa, ke viene definita "l'ipotesi di Riemann", è uno dei + importanti problemi della matematica ke ci permetterebbe di calcolare la posizione di ogni numero primo

Xmas

18-02-2005, 23:14

Originariamente inviato da damxxx è uno dei + importanti problemi della matematica ke ci permetterebbe di calcolare la posizione di ogni numero primo

non solo... tutti i sistemi di cifratura asimmetrica (chiave pubblica + chiave privata) utilizzati oggi in tutti i settori dell'informatica sarebbero spazzati via !!! :eek:

Ps. Sto leggendo anch'io quel libro !!!

;)

Banus

18-02-2005, 23:38

Originariamente inviato da Xmas
non solo... tutti i sistemi di cifratura asimmetrica (chiave pubblica + chiave privata) utilizzati oggi in tutti i settori dell'informatica sarebbero spazzati via !!! :eek:
Da quello che ho capito semplicemente permette una stima molto più precisa della distribuzione dei primi:
http://en.wikipedia.org/wiki/Prime_number_theorem

Permetterebbe una ricerca più rapida dei numeri primi, ma non di calcolarli a piacere :p
Ovviamente finchè non è dimostrata è meglio non usarla... c'è il rischio di perdersi dei numeri per strada :p

damxxx

21-02-2005, 10:16

se confermata l'ipotesi di Riemann sembra ci farebbe scoprire molte delle proprietà particolari sia dei numeri primi sia della struttura di base della matematica in genere.
Ci permetterebbe di individuare l'esatta posizione d ogni numero primo regalando, ad esempio, ad un haker una più facile e rapida strada ke porta dritto all'individuazione dei 2 numeri primi utilizzati x la crittografia con l'algoritmo RSA.

Banus

21-02-2005, 12:07

Originariamente inviato da damxxx
Ci permetterebbe di individuare l'esatta posizione d ogni numero primo regalando, ad esempio, ad un haker una più facile e rapida strada ke porta dritto all'individuazione dei 2 numeri primi utilizzati x la crittografia con l'algoritmo RSA.
Dove si dice questo? Dalle fonti che ho trovato l'ipotesi aiuterebbe molto la ricerca di numeri primi con una stima asintotica più precisa ma non al punto da determinare univocamente il numero.
La funzione zeta di Riemann è profondamente legata ai numeri primi (qui (http://en.wikipedia.org/wiki/Riemann_zeta_function#Relationship_to_prime_numbers) ). Conoscendo tutti i poli della funzione Zeta sarebbe possibile stabilire la posizione di ogni numero primo, ma l'ipotesi non riguarda questo.

dupa

21-02-2005, 14:12

Ho un mega-dubbio riguardo la stima di gauss.

Gauss diceva che i numeri primi tra 1 e N erano circa N / log N.
Secondo Gauss quindi tra 1 e 10000 ci sarebbero circa 1086 numeri primi quando in realtà ce ne sono 1.229.
Quindi Gauss dovrebbe avere sottostimato la quantità di numeri primi. (cosa coerente con ciò che sta scritto sul grafico a pagina 101 del libro)

Su http://en.wikipedia.org/wiki/Prime_number_theorem dice che:

As a consequence of the prime number theorem, one gets an asymptotic expression for the nth prime number p(n):

p(n) ~ n * ln(n)

Quindi se prendo il 1229-esimo numero primo, secondo questa formula dovrebbe stare a circa 8743, quando invece sta a circa 10000.

Quindi in base a questa seconda formula l'ipotesi di Gauss dovrebbe sovrastimare la quantità di numeri primi.

Quindi... dove sbaglio?

grazie

dupa

21-02-2005, 14:33

Ho una domanda.
Gli zeri della funzione Z di Riemann sembrano tutti stare sulla retta con componente reale pari a 1/2.

Se quando sono stati definiti i numeri complessi con i^2 = -1, fossero stati definiti con ad esempio i^2 = -3, sapere se la retta degli zeri sarebbe traslata? e verso dove?

grazie

Banus

21-02-2005, 14:40

Originariamente inviato da dupa
Quindi in base a questa seconda formula l'ipotesi di Gauss dovrebbe sovrastimare la quantità di numeri primi.

Quindi... dove sbaglio?
Le due formule non sono equivalenti, non si può passare direttamente da una all'altra. Sono entrambe asintotiche, quindi esatte solo all'infinito. Una può sottostimare e l'altra sovrastimare.

Provo a mostrarlo con i calcoli:

p(n) = n/ln(n) = N

p (circa)= n = N ln(n) >= N ln(N)

p(n) è il numero di primi da 0 a n
p è il numero primo N-esimo
Come vedi la seconda formula sovrastima, dando per buona la prima.

Per rispondere all'altra domanda: i^2 = -1 è stato fissato per semplicità. i^2 = 3 significherebbe semplicemente una compressione dell'asse immaginario di un fattore sqrt(3), ma tutto il resto sarebbe inalterato.

dupa

21-02-2005, 14:44

Originariamente inviato da Banus
Per rispondere all'altra domanda: i^2 = -1 è stato fissato per semplicità. i^2 = 3 significherebbe semplicemente una compressione dell'asse immaginario di un fattore sqrt(3), ma tutto il resto sarebbe inalterato.

Lo chiedevo perchè mi stavo facendo un po' di strippi pensando al fatto che ad esempio 17 nei complessi non è primo (considerando i^2 = -1)

17 = (4+i)(4-i)

Allora mi domandavo che tipo di influenze sulla "primalità" avesse avuto questa scelta per "i".

In secondo luogo mi domando... nei complessi esiste sempre la radice quadrata? oppure esistono dei numeri complessi per i quali la radice quadrata non è calcolabile (come non lo è nei reali per i negativi) ?

Banus

21-02-2005, 14:51

Originariamente inviato da dupa
Allora mi domandavo che tipo di influenze sulla "primalità" avesse avuto questa scelta per "i".
Il concetto di primalità ha senso solo all'interno dei numeri naturali (relativi al massimo). C è un'estensione di R e quindi parlare di numeri primi complessi non ha molto senso.

In secondo luogo mi domando... nei complessi esiste sempre la radice quadrata? oppure esistono dei numeri complessi per i quali la radice quadrata non è calcolabile (come non lo è nei reali per i negativi) ?
La radice quadrata è definita per ogni numero complesso, e non solo, anche esponenziali e logaritmi. Il problema è che in genere ha più soluzioni possibili. La radice n-esima di un numero complesso ha n radici distinte complesse.
Ad esempio 1 ha come radici cubiche 1, -1/2 + i*sqrt(3)/2, -1/2 - i*sqrt(3)/2

Ziosilvio

21-02-2005, 15:59

Originariamente inviato da Banus
Il concetto di primalità ha senso solo all'interno dei numeri naturali (relativi al massimo).
Il concetto di "elemento primo" (http://planetmath.org/encyclopedia/PrimeElement.html) ha senso in ogni anello (http://planetmath.org/encyclopedia/Ring.html).
Se poi sei in un anello euclideo (http://planetmath.org/encyclopedia/EuclideanRing.html), allora hai un equivalente del Teorema fondamentale dell'aritmetica e puoi usare l'Algoritmo Euclideo.
C è un'estensione di R e quindi parlare di numeri primi complessi non ha molto senso.
Non stai considerando C come estensione di R, ma ZxZ (con il prodotto definito come in C) come estensione di Z.

Banus

21-02-2005, 16:26

Originariamente inviato da Ziosilvio
Il concetto di "elemento primo" (http://planetmath.org/encyclopedia/PrimeElement.html) ha senso in ogni anello (http://planetmath.org/encyclopedia/Ring.html).
Se poi sei in un anello euclideo (http://planetmath.org/encyclopedia/EuclideanRing.html), allora hai un equivalente del Teorema fondamentale dell'aritmetica e puoi usare l'Algoritmo Euclideo.
I link non vanno comunque ho presente quello che stavi dicendo.
Non conoscevo però i primi gaussiani (quelli introdotti da dupa due post fa).

Non stai considerando C come estensione di R, ma ZxZ (con il prodotto definito come in C) come estensione di Z.
Ci avevo pensato. In quel caso una ridefinizione di i^2 significa scegliere un "reticolo" diverso sul piano di Gauss.

Comunque la funzione Zeta è definita su C, e i numeri primi nella sua formulazione alternativa sono quelli in N. Per quello mi sono affrettato a spostare il discorso :p

Ziosilvio

21-02-2005, 21:50

Originariamente inviato da Banus
I link non vanno
Uhm... càpita che PlanetMath si renda irreperibile.
Comunque, adesso vanno.

nin

31-08-2005, 22:48

che storia, ieri ho preso in biblioteca il libro "L'enigma dei numeri primi", e ho scoperto che anche gauss si era posto la stessa domanda :D

Son già arrivato a pagina 200!! il libro è una figata assurda, consiglio a tutti di leggerlo.

ciao

Vero! Comprato e finito in 4 giorni netti..
Ho letto su internet che una stima migliore per i primi da 0 ad N risulta essere
N/log(N-1)
Personalmente il libro mi ha infuso una profonda convizione di incompletezza per quanto riguarda la reale comprensione dei primi...convinzione derivata direttamente da Godel...

CONFITEOR

06-09-2005, 03:04

Godel ignoto? Non si contano le volte che viene citato... l'abbiamo pure visto in informatica teorica. .
bene, trovami una maglietta con su Gödel.....

Banus

06-09-2005, 06:44

bene, trovami una maglietta con su Gödel.....
http://www.geocities.com/SunsetStrip/Towers/6726/images.html :asd:
http://www.geocities.com/SunsetStrip/Towers/6726/cdman.jpghttp://upload.wikimedia.org/wikipedia/commons/1/1f/Kurt_G%C3%B6del.jpg