Formula sui numeri primi (nessuna scoperta)
Ciao a tutti vi scrivo per chiedervi una cosa, come potrete notare dal titolo l'argomento tratta su una formula per il calcolo diretto dei numeri primi.
L'ho letta da poco da wikipedia e chiedo gentilemente dei chiarimenti.
innanzitutto ecco la formula
[tex]p_n = 1 + \sum_{m=1}^{2^n}\left\lfloor \left\lfloor\frac{n}{1 + \pi(m)} \right\rfloor^\frac{1}{n}\right\rfloor.[/tex]
dove [tex]\pi(m) = \sum_{j=2}^m \frac{\sin^2(\frac{\pi}{j}((j-1)!)^2)}{\sin^2(\frac{\pi}{j})}=\sum_{j=2}^m \left\lfloor \frac{(j-1)! + 1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor \right\rfloor[/tex]
Allora mi chiedo una cosa se esiste una formula diretta per il calcolo dei numeri primi perché moltissime persone, dicono che se venisse dimostrata l'ipotesi di Riemann potrebbe essere scoperta una formula per il calcolo dei numeri primi.
Inoltre con i supercomputer di oggi questa formula non dovrebbe essere "accessibile" dal punto di vista di calcolo?
Grazie
L'ho letta da poco da wikipedia e chiedo gentilemente dei chiarimenti.
innanzitutto ecco la formula
[tex]p_n = 1 + \sum_{m=1}^{2^n}\left\lfloor \left\lfloor\frac{n}{1 + \pi(m)} \right\rfloor^\frac{1}{n}\right\rfloor.[/tex]
dove [tex]\pi(m) = \sum_{j=2}^m \frac{\sin^2(\frac{\pi}{j}((j-1)!)^2)}{\sin^2(\frac{\pi}{j})}=\sum_{j=2}^m \left\lfloor \frac{(j-1)! + 1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor \right\rfloor[/tex]
Allora mi chiedo una cosa se esiste una formula diretta per il calcolo dei numeri primi perché moltissime persone, dicono che se venisse dimostrata l'ipotesi di Riemann potrebbe essere scoperta una formula per il calcolo dei numeri primi.
Inoltre con i supercomputer di oggi questa formula non dovrebbe essere "accessibile" dal punto di vista di calcolo?
Grazie
Risposte
Non so nulla di quella formula, mi viene da dire che trova solo alcuni numeri primi.
Come ad esempio fa quest'altra formula: http://it.wikipedia.org/wiki/Numero_primo_di_Mersenne
Anche solo capire se un numero n è primo non è un compito facile, neanche per un calcolatore.
Con n molto grande, serve un certo lasso di tempo per calcolare i suoi fattori primi anche con un PC e su questa difficoltà si basa la crittografia moderna su internet.
Come ad esempio fa quest'altra formula: http://it.wikipedia.org/wiki/Numero_primo_di_Mersenne
Anche solo capire se un numero n è primo non è un compito facile, neanche per un calcolatore.
Con n molto grande, serve un certo lasso di tempo per calcolare i suoi fattori primi anche con un PC e su questa difficoltà si basa la crittografia moderna su internet.
In effetti pensandoci sono rimasto molto sorpreso anch'io quando sul web ho cercato "formula per il calcolo dei numeri primi"
la formula non l'ho ancora provata anche perché credo che usi un sacco di tempo quando il numero da trovare è in un'alta posizione.
Su wiki c'è scritto "dal teorema di Wilson si può ricavare una formula per il calcolo diretto dei numeri primi"
http://it.wikipedia.org/wiki/Formula_per_i_numeri_primi
Qua c'è scritto anche un'altra cosa, "dal teorema di Wilson si può ricavare facilmente una formula per il calcolo dei numeri primi minori di x"
http://it.wikipedia.org/wiki/Teorema_di_Wilson
Mah.... il tutto mi sembra strano.
la formula non l'ho ancora provata anche perché credo che usi un sacco di tempo quando il numero da trovare è in un'alta posizione.
Su wiki c'è scritto "dal teorema di Wilson si può ricavare una formula per il calcolo diretto dei numeri primi"
http://it.wikipedia.org/wiki/Formula_per_i_numeri_primi
Qua c'è scritto anche un'altra cosa, "dal teorema di Wilson si può ricavare facilmente una formula per il calcolo dei numeri primi minori di x"
http://it.wikipedia.org/wiki/Teorema_di_Wilson
Mah.... il tutto mi sembra strano.
Spero che la spiegazione di queste formule non sia deludente:
Il teorema di Wilson dice che per un intero $n > 1$ si ha che
$(n-1)! = -1$ modulo $n$ \(\qquad\quad\) se $n$ e' primo
\(\qquad\qquad\quad\) $= 2$ modulo $n$ \(\qquad\quad\) se $ n=4$
\(\qquad\qquad\quad\) $ = 0$ modulo $n$ \(\qquad\quad\) se $n$ non e' primo e non e' $4$.
La dimostrazione elementare si trova sulla pagina di wikipedia.
Per le proprieta' ben note della funzione $\sin (\pi x)$, la formula di Wilson implica che
$\sin((n-1)! pi/n) = \sin(pi/n)$ (a meno di segno) se $n$ e' primo
\(\qquad\qquad\qquad\qquad\qquad\) $= -1$ \(\qquad\quad\) se $n=4$
\(\qquad\qquad\qquad\qquad\qquad\) $= 0$ \(\qquad\qquad\) se $n$ non e' primo e non e' $4$
Se scriviamo quindi
$F(n) = \sin((n-1)! pi/n)^2 / \sin(pi/n)^2$,
si ha che
$F(n)= 1$ \(\qquad\quad\) se $n$ e' primo
\(\qquad\quad\) $ = 2$ \(\qquad\quad\) se $n=4$
\(\qquad\quad\) $= 0 $ \(\qquad\quad\) se $n$ non e' primo e non e' $4$
Quindi, a parte il caso $n=4$, la funzione $F(n)$ "vede" se $n$ e' primo o meno.
Non sara' un miracolo che con una funzione del genere e' possibile
fabbricare delle formule per il k-esimo primo e per il numero
di primi $< X$.... etc.
Queste formule non sono utili da un punto di vista computazionale,
perche' non si sa calcolare in modo efficiente $n!$ se $n$ e' molto grande.
Il teorema di Wilson dice che per un intero $n > 1$ si ha che
$(n-1)! = -1$ modulo $n$ \(\qquad\quad\) se $n$ e' primo
\(\qquad\qquad\quad\) $= 2$ modulo $n$ \(\qquad\quad\) se $ n=4$
\(\qquad\qquad\quad\) $ = 0$ modulo $n$ \(\qquad\quad\) se $n$ non e' primo e non e' $4$.
La dimostrazione elementare si trova sulla pagina di wikipedia.
Per le proprieta' ben note della funzione $\sin (\pi x)$, la formula di Wilson implica che
$\sin((n-1)! pi/n) = \sin(pi/n)$ (a meno di segno) se $n$ e' primo
\(\qquad\qquad\qquad\qquad\qquad\) $= -1$ \(\qquad\quad\) se $n=4$
\(\qquad\qquad\qquad\qquad\qquad\) $= 0$ \(\qquad\qquad\) se $n$ non e' primo e non e' $4$
Se scriviamo quindi
$F(n) = \sin((n-1)! pi/n)^2 / \sin(pi/n)^2$,
si ha che
$F(n)= 1$ \(\qquad\quad\) se $n$ e' primo
\(\qquad\quad\) $ = 2$ \(\qquad\quad\) se $n=4$
\(\qquad\quad\) $= 0 $ \(\qquad\quad\) se $n$ non e' primo e non e' $4$
Quindi, a parte il caso $n=4$, la funzione $F(n)$ "vede" se $n$ e' primo o meno.
Non sara' un miracolo che con una funzione del genere e' possibile
fabbricare delle formule per il k-esimo primo e per il numero
di primi $< X$.... etc.
Queste formule non sono utili da un punto di vista computazionale,
perche' non si sa calcolare in modo efficiente $n!$ se $n$ e' molto grande.
Quindi la formula funziona eccome. Cioè trova l'n-esimo numero primo.
Senta @Stickelberg potrebbe farmi verdere un esempio? di come funziona la formula?.
Senta @Stickelberg potrebbe farmi verdere un esempio? di come funziona la formula?.
Esistono "formule" per determinare i numeri primi ma esse coinvolgono sommatorie di parti intere: in pratica esse sono inutili per il fatto che i termini che compaiono nelle sommatorie crescono al crescere di n e tali somme non si riescono a semplificare, come invece accade per molte altre sommatorie. Sul sito http://www.raimondovaleri.it, nella sezione articoli di matematica, puoi trovare una "formula" che fornisce o numeri primi o numeri non interi e un'altra che ti permette, in linea di principio, applicando un opportuno operatore su n, di ottenere sempre un numero primo. Purtroppo queste formule coinvolgono sempre sommatorie da 1 a n, di parti intere: sono tutte praticamente inutili. Ti consiglio anche di veder il file pdf: http://www.math.unipr.it/~zaccagni/psfi ... dn2005.pdf in cui a pagina 30,si parla anche di "formule" per i numeri primi. Questo file è molto tecnico e difficile mentre
gli articoli di matematica, scaricabili dal sito http://www.raimondovaleri.it, sono elementari.
gli articoli di matematica, scaricabili dal sito http://www.raimondovaleri.it, sono elementari.
Grazie dei link.
Per ora possiamo concludere che non c'è una formula semplice che determina tutti i numeri primi in modo semplificativo giusto?
Per ora possiamo concludere che non c'è una formula semplice che determina tutti i numeri primi in modo semplificativo giusto?
Purtroppo è così
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo