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

$y=2\cdot n+1$

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 $y=m\cdot x+c$, 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, Template:Citazione necessaria:

• 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

$P(1+kp)\equiv P(1)modp\equiv 0modp$

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

$n^2+n+41$

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,, 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:

$6171054912832631+366384\cdot \left(\prod _{p\le 23}p\right)\cdot n=6171054912832631+81737658082080n$

dove $\prod _{p\le 23}p$ 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 che un intero k+2 è primo se e solo se è risolubile nei numeri naturali il seguente sistema di equazioni diofantee

$0=wz+h+j-q$

$0=(gk+2g+k+1)(h+j)+h-z$

$0=16(k+1{)}^3(k+2)(n+1{)}^2+1-f^2$

$0=2n+p+q+z-e$

$0=e^3(e+2)(a+1{)}^2+1-o^2$

$0=(a^2-1)y^2+1-x^2$

$0=16r^2{y}^4(a^2-1)+1-u^2$

$0=n+l+v-y$

$0=(a^2-1)l^2+1-m^2$

$0=ai+k+1-l-i$

$0=((a+u^2(u^2-a){)}^2-1)(n+4dy{)}^2+1-(x+cu{)}^2$

$0=p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m$

$0=q+y(a-p-1)+s(2ap+2a-p^2-2p-2)-x$

$0=z+pl(a-p)+t(2ap-p^2-1)-pm$

portando al polinomio in 26 variabili con la proprietà desiderata

$(k+2)\{(wz+h+j-q{)}^2-[(gk+2g+k+1)(h+j)+h-z{]}^2+$

$-[16(k+1{)}^3(k+2)(n+1{)}^2+1-f^2{]}^2-(2n+p+q+z-e{)}^2+$

$-[e^3(e+2)(a+1{)}^2+1-o^2{]}^2-[(a^2-1)y^2+1-x^2{]}^2+$

$-[16r^2{y}^4(a^2-1)+1-u^2{]}^2-(n+l+v-y{)}^2-[(a^2-1)l^2+1-m^2{]}^2+$

$-(ai+k+1-l-i{)}^2-\{\{[a+u^2(u^2-a){]}^2-1\}(n+4dy{)}^2+1+$

${-(x+cu{)}^2\}}^2-[p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m{]}^2+$

$-[q+y(a-p-1)+s(2ap+2a-p^2-2p-2)-x{]}^2-[z+pl(a-p)+$

$+t(2ap-p^2-1)-pm{]}^2\}$

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:

Variabili	Grado	Autore	Anno	Note
24	37	Matijasevič	1971	Non esplicitato
21	21	Matijasevič	1971
26	25	Jones, Sato, Wada e Wiens	1976	Primo in forma esplicita
42	5	Jones, Sato, Wada e Wiens	1976	Grado più basso (non esplicitato)
12	13697	Matijasevič	1976
10	circa Template:M	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 $\theta$ (detta costante di Mills) tale che

$\lfloor {\theta }^{3^n}\rfloor$

(dove $\lfloor x\rfloor$ 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.

Un'altra formula, fornita da Wright, che genera solo primi per n ≥ 1, è

$\lfloor 2^{2^{2^{{.}^{{.}^{{.}^{2^{\omega }}}}}}}\rfloor$

(2 elevato alla 2 n volte, elevato alla ω) con ω=1.9287800...

Formule attraverso le frazioni

È possibile produrre numeri primi attraverso le quattordici frazioni $\frac{17}{91}\frac{78}{85}\frac{19}{51}\frac{23}{38}\frac{29}{33}\frac{77}{29}\frac{95}{23}\frac{77}{19}\frac{1}{17}\frac{11}{13}\frac{13}{11}\frac{15}{14}\frac{15}{2}\frac{55}{1}$

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.

Formule derivanti dal teorema di Wilson

Template:F 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

$\pi (m)=\sum _{j=2}^m\lfloor \frac{(j-1)!+1}{j}-\lfloor \frac{(j-1)!}{j}\rfloor \rfloor$

La formula porta ad una formula diretta per lTemplate:'n-esimo numero primo:

$p_n=1+\sum _{m=1}^{2^n}\lfloor {\lfloor \frac{n}{1+\pi (m)}\rfloor }^{\frac{1}{n}}\rfloor .$

Sempre sul teorema di Wilson è basata la funzione

$f(n)=2+(2(n!)mod(n+1))$

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 forniscono la formula

$p_n=1+\sum _{j=1}^{2^n}f(n,\pi (j))$

dove f(x,y) è 0 se x=y ed è invece uguale a $\frac{1}{2}\lfloor 1+\frac{x-y}{|x-y|}\rfloor$ altrimenti.

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

• Test di primalità
• Teorema di Dirichlet

Collegamenti esterni

• Template:Collegamenti esterni