In matematica, e più precisamente in teoria analitica dei numeri, la funzione enumerativa dei primi (o funzione pi greco) è una funzione aritmetica che associa a ogni numero reale il numero dei numeri primi non superiori a . È tradizionalmente denotata con il simbolo (che non ha alcuna relazione con il numero π).
Essendo una funzione a gradino, la funzione enumerativa dei numeri primi è un importante oggetto di studio in quanto permette di analizzare la distribuzione dei numeri primi all'interno dell'insieme dei numeri naturali. La relativa successione di interi, definita sui naturali, è presente nella OEIScon la sigla
Storia Alla fine del XVIII secolo, i matematici Carl Friedrich Gauss e Adrien-Marie Legendre ipotizzarono, indipendentemente l'uno dall'altro, che la densità dei numeri primi decrescesse asintoticamente come il logaritmo naturale. In particolare, congetturarono che per tendente all'infinito, il valore di si approssimasse al rapporto tra e il logaritmo naturale di .
Tale congettura fu dimostrata nel 1896 da Jacques Hadamard e Charles Jean de la Vallée-Poussin, prendendo il nome di teorema dei numeri primi.
Primi valori I primi valori assunti dalla funzione in corrispondenza dei primi cento numeri interi positivi (da n = 1 a n = 100) sono riportati nella seguente tabella:
+ Valori di per n da 1 a 100 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 0+ 0 1 2 2 3 3 4 4 4 4 10+ 5 5 6 6 6 6 7 7 8 8 20+ 8 8 9 9 9 9 9 9 10 10 30+ 11 11 11 11 11 11 12 12 12 12 40+ 13 13 14 14 14 14 15 15 15 15 50+ 15 15 16 16 16 16 16 16 17 17 60+ 18 18 18 18 18 18 19 19 19 19 70+ 20 20 21 21 21 21 21 21 22 22 80+ 22 22 23 23 23 23 23 23 24 24 90+ 24 24 24 24 24 24 25 25 25 25
Stime asintotiche
Lo studio del comportamento asintotico di costituisce uno degli argomenti principali della teoria analitica dei numeri. Il teorema dei numeri primi stabilisce che:
Un'approssimazione ancora più rigorosa, dimostrata da Hadamard e de la Vallée Poussin, fa uso del logaritmo integrale:
dove la funzione è definita come l'integrale
L'ipotesi di Riemann, uno dei più importanti problemi aperti della matematica, predice che valga una versione estremamente precisa di tale risultato, limitando il margine d'errore dell'approssimazione secondo la formula
utilizzando la notazione O grande.
Disuguaglianze, maggioranti e minoranti Oltre alle approssimazioni asintotiche, esistono diverse disuguaglianze che limitano il valore della funzione enumerativa dei primi. Il matematico J. Barkley Rosser dimostrò nel 1941 maggioranti e minoranti stretti per . Per ogni vale la disuguaglianza:
Queste stime dall'alto e dal basso si rivelano particolarmente utili nell'ambito dell'informatica teorica e dell'analisi della complessità computazionale degli algoritmi che operano con la fattorizzazione o la crittografia.
Note
Voci correlate Numero primo Teorema dei numeri primi Teoria analitica dei numeri Funzione zeta di Riemann Crivello di Eratostene
Altri progetti
Collegamenti esterni
Categoria:Numeri primi Categoria:Funzioni aritmetiche