Formula generatrice di numeri primi
Giuseppe Pipino
Nella sua comunicazione al NG, Antonio Ruggero chiede:
>mi sono sempre domandato....
>come mai nessuno riesce a trovare una formula generatrice di numeri primi
??
>Dov'è la difficoltà ??
Non mi pare che sia esatto dire che non esista una formula che generi i
numeri primi.
Infatti Sierpinski (1952) dopo aver definito la costante
A=somma(n=1,infinito) pn*10^(-2)^n (=0.0203005..)
dimostra che l'ennesimo primo è
pn=[A*10^2^n-10^2^(n-1)*[A*10^2^(n-1)]
dove la scrittura [x] indica il massimo intero minore od uguale ad x .
A me sembra che la difficoltà consista nel fatto che questa formula (come
altre simili che sono state proposte) presenti difficoltà esponenziali di
calcolo (cioè al crescere di n il tempo di calcolo aumenta
esponenzialmente).
Invito chi conosce degli algoritmi abbordabili per la ricerca di GRANDI
PRIMI a metterli a disposizione del NG.
Ciao.
Giuseppe Pipino
xyxyxy
>Non mi pare che sia esatto dire che non esista una formula che generi i
>numeri primi.
>Infatti Sierpinski (1952) dopo aver definito la costante
>A=somma(n=1,infinito) pn*10^(-2)^n (=0.0203005..)
>dimostra che l'ennesimo primo è
>pn=[A*10^2^n-10^2^(n-1)*[A*10^2^(n-1)]
>dove la scrittura [x] indica il massimo intero minore od uguale ad x .
Il punto e' che la formula contiene pn, e quindi non risolve il
problema.
oha
wrote:
:)Invito chi conosce degli algoritmi abbordabili per la ricerca di GRANDI
:)PRIMI a metterli a disposizione del NG.
si potrebbe usare il piccolo teorema di Fermat per stabilire se un
numero e' probabilmente primo.
che io sappia, c'e' il test di lucas che verifica abbastanza
velocemente se un numero nella forma h*a^p e' primo (con p primo) ma
non ho mai trovato algoritmi per la verifica di un numero p generico
Oha