Formula per i numeri primi

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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

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

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

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

È 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[modifica | modifica wikitesto]

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

Hardy e Wright[9] forniscono la formula

dove f(x,y) è 0 se x=y ed è invece uguale a altrimenti.

Note[modifica | modifica wikitesto]

  1. ^ Wolfram MathWorld, Prime-Generating Polynomial, su mathworld.wolfram.com.
  2. ^ Devlin, in Dove va la matematica, p.73
  3. ^ 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).
  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 0-19-853171-0.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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