Formula per i numeri primi

Da Wikipedia, l'enciclopedia libera.

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 è stata per secoli l'obiettivo di tanti studiosi, sia professionisti che dilettanti, ma 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 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).

Questa funzione è un esempio di una classe di funzioni polinomiali di primo grado a coefficienti costanti, in grado di generare un'infinità numerabile di numeri primi, non completa (non include tutti i numeri primi) e non univoca (include anche numeri composti):

y = m \cdot x + c, dove c è un numero naturale, m e c sono numeri coprimi.
c può essere negativo (ad esempio  c= -1) e m un prodotto di numeri primi. Un altro esempio è la funzione: y = 6 \cdot n  - 1.

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[modifica | modifica sorgente]

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)\mod p\equiv 0\mod p

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

6171054912832631 + 366384 \cdot \left( \prod_{p \leq 23} p \right) \cdot n=6171054912832631 + 81737658082080n [3]

dove \prod_{p \leq 23} p indica il prodotto di tutti i primi minori o uguali a 23.

Formule basate sulle equazioni diofantee[modifica | modifica sorgente]

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

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^2y^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) \left \{ {( wz + h + j - q)^2 - [ (gk + 2g + k + 1)(h + j) + h - z]^2 + }\right.
- [ 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^2y^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- \left\{ { \{[a + u^2(u^2 - a)]^2 - 1\}(n + 4dy)^2 + 1 +}\right.
\left. {- (x + cu)^2} \right\}^2  - [ p + l(a - n - 1)+ b(2an + 2a - n^2 - 2n - 2) - m]^2 +
\left. {- [ q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x]^2 - [ z + pl(a - p) +} \right.
\left. {+ t(2ap - p^2 - 1) - pm]^2} \right \}

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[modifica | modifica sorgente]

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.[6]

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...[7]

Formule attraverso le frazioni[modifica | modifica sorgente]

È possibile produrre numeri primi attraverso le quattordici frazioni \frac{17}{91}\quad\frac{78}{85}\quad\frac{19}{51}\quad\frac{23}{38} \quad\frac{29}{33}\quad\frac{77}{29}\quad\frac{95}{23} \quad\frac{77}{19}\quad\frac{1}{17}\quad\frac{11}{13}\quad\frac{13}{11}\quad\frac{15}{14}\quad\frac{15}{2}\quad\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.[8]

Formule derivanti dal teorema di Wilson[modifica | modifica sorgente]

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 \left\lfloor \frac{(j-1)! + 1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor \right\rfloor

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

p_n = 1 + \sum_{m=1}^{2^n}\left\lfloor \left\lfloor\frac{n}{1 + \pi(m)} \right\rfloor^\frac{1}{n}\right\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[modifica | modifica sorgente]

Hardy e Wright[9] 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}\left\lfloor 1+\frac{x-y}{|x-y|}\right\rfloor altrimenti.

Voci correlate[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ Wolfram MathWorld, Prime-Generating Polynomial.
  2. ^ Devlin, in Dove va la matematica, p.73
  3. ^ Jens Kruse Andersen, "Primes in Arithmetic Progression Records. URL consultato il 2009.06.23.
  4. ^ 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
  5. ^ Paulo Ribenboim, The little book of big primes, 1996, p. 116, ISBN 3-540-97042-8.
  6. ^ La dimostrazione di Caldwell e Cheng
  7. ^ Wright, E.M., A Prime-Representing Function in American Mathematical Monthly, nº 58, 1951, pp. 616-618.
  8. ^ Conway e Guy, p.126-127
  9. ^ Godfrey Harold Hardy, Edward Maitland Wright, An Introduction to the Theory of Numbers, 5ª ed., Oxford, Clarendon Press, 1979, ISBN 0198531710.

Bibliografia[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica