Formula per i numeri primi
Una formula per i numeri primi è un'espressione che consenta di distinguere nell'ambito degli interi positivi tutti i numeri primi e solo essi. La ricerca di una tale formula è da secoli l'obiettivo di tanti studiosi, sia professionisti che dilettanti, e finora non è nota alcuna formula semplice di questo tipo. Per contro negli ultimi decenni lo studio dei numeri primi si è servito sempre più sistematicamente di attività sperimentali condotte con il computer.
Per avere un'idea del problema, è bene chiarire che è semplice trovare una funzione o una classe di funzioni che generi un'infinità numerabile di numeri primi, a partire da una variabile che è un numero naturale o un numero primo: la difficoltà è trovare una funzione che generi esclusivamente numeri primi, e in secondo luogo, che li generi tutti. Ad esempio la funzione
dove n è un numero naturale, genera evidentemente l'insieme di tutti i numeri dispari, e quindi tutti i numeri primi, escluso 2, che di questo sono un sottoinsieme; tuttavia genera anche numeri composti, anche nel caso che n sia un numero primo (ad esempio per n = 13). Allo stesso modo, tutti i polinomi di primo grado , dove c è un numero naturale e m e c sono coprimi, generano infiniti numeri primi (teorema di Dirichlet) ma anche numeri composti.
La formula dei numeri primi dovrebbe avere le seguenti caratteristiche, in ordine di importanza[senza fonte]:
- estensione della variabile indipendente: generare un'infinità numerabile di numeri primi;
- esclusività (rispetto alla variabile indipendente): generare solamente numeri primi e nessun numero composto;
- generalità (rispetto alla variabile indipendente): generare tutti i numeri primi superiori a un certo valore (numero primo, dispari, o meglio naturale e intero), anziché un sottoinsieme di numeri primi;
- estensione (del dominio) della variabile indipendente: generare numeri primi a partire dall'insieme più vasto possibile di valori (numeri naturali o meglio interi, anche negativi), piuttosto che da un sottoinsieme (x numero dispari o numero primo)
Formule polinomiali
Si dimostra che non esiste alcun polinomio non costante a valori interi che generi esclusivamente numeri primi: infatti, se questo esistesse (sia ad esempio P(n)), allora P(1)=p sarebbe primo. Ma allora
in quanto aggiungere dei multipli di p non varia la congruenza modulo p. P(1+kp) sarebbe allora primo e divisibile per p, cioè sarebbe proprio uguale a p. Ma allora P(n) assumerebbe infinite volte lo stesso valore, cosa impossibile per il principio d'identità dei polinomi.
Esistono tuttavia polinomi che generano molti più numeri primi della media: un caso limite è quello del polinomio
- [1]
che assume valori primi per ogni n compreso tra 0 e 39, mentre per n=40 e n=41 si hanno numeri composti. Nei primi 10 milioni di valori che questa funzione assume circa 1/3 sono primi,[2], ma non è stato ancora dimostrato che ne esistano infiniti. Non è stato ancora dimostrato che alcun polinomio di grado maggiore o uguale di 2 assuma infiniti valori primi.
Il teorema di Dirichlet afferma invece che questa proprietà vale per ogni polinomio di primo grado an+b, nel caso che a e b siano coprimi. Il teorema di Green-Tao migliora questo risultato, affermando che per ogni k esiste un L(n)=an+b che assume valori primi per n che varia da 0 a k-1. Il miglior risultato noto è per k=25:
- [3]
dove indica il prodotto di tutti i primi minori o uguali a 23.
Formule basate sulle equazioni diofantee
A seguito della dimostrazione del teorema di Matijasevič (soluzione del decimo problema di Hilbert), avvenuta nel 1970, sono stati trovati vari polinomi i cui valori positivi sono sempre numeri primi. Matijasevič dimostrò l'esistenza di un polinomio di 37º grado in 24 incognite, ma senza esplicitarlo; nel 1976 James P. Jones, Daihachiro Sato, Hideo Wada e Douglas Wiens hanno dimostrato[4] che un intero k+2 è primo se e solo se è risolubile nei numeri naturali il seguente sistema di equazioni diofantee
portando al polinomio in 26 variabili con la proprietà desiderata
che però assume quasi sempre valori negativi. In seguito sono stati trovati altri polinomi con questa proprietà, riuscendo a diminuire o il numero delle variabili o il grado, ma non entrambi contemporaneamente; la tabella seguente mostra i progressi in questo campo:[5]
Variabili | Grado | Autore | Anno | Note |
---|---|---|---|---|
24 | 37 | Matijasevič | 1971 | Non esplicitato |
21 | 21 | Matijasevič | 1971 | |
26 | 25 | Jones, Sato, Wada e Wiens[4] | 1976 | Primo in forma esplicita |
42 | 5 | Jones, Sato, Wada e Wiens | 1976 | Grado più basso (non esplicitato) |
12 | 13697 | Matijasevič | 1976 | |
10 | circa 1,6×1045 | Matijasevič | 1976 | Minor numero di variabili (non esplicitato) |
Formule esponenziali
Alcune formule si basano sull'uso di funzioni esponenziali.
Il teorema di Mills afferma che esiste una costante (detta costante di Mills) tale che
(dove indica la parte intera di x) è sempre un numero primo per ogni scelta di n. Non si conosce nessuna formula semplice per il calcolo della costante di Mills θ; le approssimazioni attualmente utilizzate si basano sulla sequenza dei cosiddetti primi di Mills (i numeri primi generati tramite questa formula). Assumendo per vera l'ipotesi di Riemann, è stato possibile calcolare fino a 7000 cifre decimali di questa costante.[6]
Un'altra formula, fornita da Wright, che genera solo primi per n ≥ 1, è
(2 elevato alla 2 n volte, elevato alla ω) con ω=1.9287800...[7]
Formule attraverso le frazioni
È possibile produrre numeri primi attraverso le quattordici frazioni
Partendo da 2, l'algoritmo consiste nel moltiplicare per la prima frazione che dia un numero intero, e di ripetere questo procedimento col numero ottenuto, e così via. Gli esponenti delle potenze di due ottenute saranno precisamente i numeri primi, nell'esatto ordine della loro sequenza.[8]
Formule derivanti dal teorema di Wilson
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
Alcune formule possono essere ricavate dal teorema di Wilson, sebbene queste siano molto poco efficienti rispetto ai test di primalità oggi in uso.
π(n), la funzione enumerativa dei primi (che indica, per ogni n, il numero di primi minori o uguali a n), può essere calcolata anche come
La formula porta ad una formula diretta per l'n-esimo numero primo:
Sempre sul teorema di Wilson è basata la funzione
i cui valori per n intero positivo sono soltanto numeri primi: in particolare, 2 è generato molte volte, mentre ogni primo p solamente da n=p-1.
Infatti, se n+1 è composto allora divide n!, e quindi f(n)=2; se invece n+1 è primo, per il teorema di Wilson n! è congruo a (n+1)-1 modulo n+1, e quindi 2(n!) è congruo a n-1. Quindi f(n)=2+n-1=n+1 che è primo per ipotesi.
Altre formule
Hardy e Wright[9] forniscono la formula
dove f(x,y) è 0 se x=y ed è invece uguale a altrimenti.
Note
- ^ Wolfram MathWorld, Prime-Generating Polynomial, su mathworld.wolfram.com.
- ^ Devlin, in Dove va la matematica, p.73
- ^ Jens Kruse Andersen, "Primes in Arithmetic Progression Records, su hjem.get2net.dk. URL consultato il 2009.06.23 (archiviato dall'url originale il 22 febbraio 2008).
- ^ a b James P. Jones, Daihachiro Sato, Hideo Wada, Douglas Wiens: Diophantine representation of the set of prime numbers (1976), American Mathematical Monthly 83: 449–464
- ^ Paulo Ribenboim, The little book of big primes, 1996, p. 116, ISBN 3-540-97042-8.
- ^ La dimostrazione di Caldwell e Cheng
- ^ Wright, E.M., A Prime-Representing Function, in American Mathematical Monthly, n. 58, 1951, pp. 616-618.
- ^ Conway e Guy, p.126-127
- ^ Godfrey Harold Hardy, Edward Maitland Wright, An Introduction to the Theory of Numbers, 5ª ed., Oxford, Clarendon Press, 1979, ISBN 0-19-853171-0.
Bibliografia
- Keith Devlin, Dove va la matematica. Bollati Boringhieri, Torino, 1994. ISBN 8833911829
- John H. Conway, Richard K. Guy, Il libro dei numeri. Hoepli, Milano, 1999. ISBN 8820325195
Voci correlate
Collegamenti esterni
- (EN) Eric W. Weisstein, Formula per i numeri primi, su MathWorld, Wolfram Research.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)