La fabbrica dei numeri primi
La seguente funzione $F(k)=\floor((cos(pi*((k-1)!+1)/k))^2)$ ritorna $1$ se $k$ è primo, altrimenti $0$.
Tramite questa funzione, possiamo calcolare l'ennesimo primo così
[size=150]$p_n=1+sum_(m=1)^(2^n) \floor((n/(sum_(k=1)^m F(k)))^(1/n))$[/size]
[ot]Nota: Ho visto che nel Forum ci sono già state molte discussioni riguardo a "curiosità matematiche", peraltro tutte abbastanza vecchie, quindi ho deciso né di riesumarle né di intitolare questa allo stesso modo però penserei di utilizzare questa per questo scopo.[/ot]
Cordialmente, Alex
Tramite questa funzione, possiamo calcolare l'ennesimo primo così
[size=150]$p_n=1+sum_(m=1)^(2^n) \floor((n/(sum_(k=1)^m F(k)))^(1/n))$[/size]
[ot]Nota: Ho visto che nel Forum ci sono già state molte discussioni riguardo a "curiosità matematiche", peraltro tutte abbastanza vecchie, quindi ho deciso né di riesumarle né di intitolare questa allo stesso modo però penserei di utilizzare questa per questo scopo.
[/ot] Cordialmente, Alex
Risposte
Commenti interessanti,
grazie a tutte\i.
grazie a tutte\i.
"hydro":
... non esistono polinomi che assumono solo valori primi...
Appunto, era questo il senso del post di Martino.
Beh ma ti dice solo che se il polinomio valutato in $[...k...]$ è positivo allora $k$ è primo, non ti dice che se $k$ è primo allora il polinomio valutato in $[..k..]$ è positivo. Quindi non è un di primalità, è qualcosa in meno. "Polinomio che genera primi" è una dicitura estremamente vaga, e comunque (come c'è anche scritto in quel link ed è anche un facile esercizio dimostrare) non esistono polinomi che assumono solo valori primi...
In quel link viene riportato il polinomio di Jones, Sato, Wada and Wiens, di $25°$ grado in $26$ variabili.
È composto da due fattori: $k+2$ e l'altro .. questo "altro" è composto da $+1$ seguito da una serie di quadrati preceduti dal segno meno ovvero l'unico modo per produrre un risultato non negativo è che siano tutti nulli e quindi che il primo che ne risulta è uguale a $k+2$
In pratica mi serve per testare se $k+2$ è primo
Peraltro, per quel che sapevo, per "polinomio che genera primi" si intende un polinomio che genera SOLO primi (come intendeva esserlo quello famoso di Eulero)
È composto da due fattori: $k+2$ e l'altro .. questo "altro" è composto da $+1$ seguito da una serie di quadrati preceduti dal segno meno ovvero l'unico modo per produrre un risultato non negativo è che siano tutti nulli e quindi che il primo che ne risulta è uguale a $k+2$
In pratica mi serve per testare se $k+2$ è primo
Peraltro, per quel che sapevo, per "polinomio che genera primi" si intende un polinomio che genera SOLO primi (come intendeva esserlo quello famoso di Eulero)
"axpgn":
Io non ho ancora capito se c'è o non c'è
EDIT: Penso di aver capito
Boh mi sembra tutto abbastanza chiaro: è un polinomio $P(X)$ tale che se $x_0$ è un vettore di interi non negativi, allora $P(x_0)$ è o primo o negativo. Inoltre al variare di $x_0$ tra tutti i vettori di interi non negativi, l'insieme dei $P(x_0)$ contiene quello di tutti i primi. Che c'entra con i test di primalità?
Io non ho ancora capito se c'è o non c'è 
EDIT: Penso di aver capito : in pratica il polinomio di Matijasevic (e quelli simili) sono dei test di primalità, non generano (sempre) numeri primi.
EDIT: Penso di aver capito
: in pratica il polinomio di Matijasevic (e quelli simili) sono dei test di primalità, non generano (sempre) numeri primi.
Grazie, non lo conoscevo. 
Ho letto male, stavo pensando al fatto che non esiste nessun polinomio (con un qualsiasi numero di variabili) che assume come valore un numero primo quando valutato su qualsiasi intero non negativo.
Ho letto male, stavo pensando al fatto che non esiste nessun polinomio (con un qualsiasi numero di variabili) che assume come valore un numero primo quando valutato su qualsiasi intero non negativo.
"Martino":
[quote="j18eos"]Ricordo che Courant & Robbins, nel loro libro, dichiararono l'esistenza di\scrissero una formula polinomiale in 26 variabili; l'unica condizione è che il polinomio dev'essere valutato sui numeri interi positivi, e che i risultati positivi sono tutti e i soli numeri primi!
Se ricordo bene è un facile esercizio mostrare che un tale polinomio non può esistere.[/quote]
Come no, esiste eccome: è il famoso polinomio di Matijasevic.
"j18eos":
Ricordo che Courant & Robbins, nel loro libro, dichiararono l'esistenza di\scrissero una formula polinomiale in 26 variabili; l'unica condizione è che il polinomio dev'essere valutato sui numeri interi positivi, e che i risultati positivi sono tutti e i soli numeri primi!
Se ricordo bene è un facile esercizio mostrare che un tale polinomio non può esistere.
Ricordo che Courant & Robbins, nel loro libro, dichiararono l'esistenza di\scrissero una formula polinomiale in 26 variabili; l'unica condizione è che il polinomio dev'essere valutato sui numeri interi positivi, e che i risultati positivi sono tutti e i soli numeri primi!
"axpgn":
Di Wilson lo sapevo (l'ho notato
Quello della formula
Di Wilson lo sapevo (l'ho notato ) ma Willans chi è?
) ma Willans chi è?
Si chiama formula di Willans che usa il teorema di Wilson
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo