Formule pour les nombres premiers

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, il est connu qu'aucune fonction polynôme non-constante P(n) n'existe pour exprimer la primalité d'un entier n donné (ou même presque tous les n). En utilisant la théorie algébrique des nombres, nous pouvons être un peu plus précis.

Le polynôme quadratique

$P(n) = n^2 + n + 41\,$

est premier pour tous les entiers positifs inférieurs à 40. Les nombres premiers pour n = 0, 1, 2, 3... sont 41, 43, 47, 53, 61, 71... Les différences entre les termes sont 2, 4, 6, 8, 10... Pour n = 40, il produit un carré, 1681, qui est égal à 41×41, le plus petit nombre composé pour cette formule. En fait, si 41 divise n il divise P(n) aussi. Le phénomène est lié à la spirale d'Ulam, qui est aussi quadratique implicitement, et aux nombre de classes.

Un ensemble d'équations diophantiennes de 26 variables peut être utilisé pour obtenir des nombres premiers : un nombre donné k + 2 est premier ssi le système suivant d'équations diophantiennes possède une solution dans l'ensemble des entiers naturels (Riesel, 1994):

0 = w z + h + j - q

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

0 = (16 k + 1) 3 (k + 2)(n + 1) 2 + 1 - f 2

0 = 2 n + 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 = 16 r 2 y 4 (a 2 - 1) + 1 - u 2

0 = n + l + v - y

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

0 = a i + k + 1 - l - i

0 = ((a + u 2 (u 2 - a)) 2 - 1)(n + 4 d y) 2 + 1 - (x + c u) 2

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

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

0 = z + p l (a - p) + t (2 a p - p 2 - 1) - p m

La fonction suivante produit tous les nombres premiers, et seulement les nombres premiers, pour les entiers positifs n :

$f(n) = 2 + (2(n!) \operatorname{mod} (n+1))$

Cette formule est basée sur le théorème de Wilson ; le nombre deux est généré beaucoup de fois et tous les autres nombres premiers sont généré exactement une fois par cette fonction. (En fait un nombre premier p est généré pour n = (p − 1) et 2 autrement (c.a.d. quand n + 1 est composé))

En utilisant la fonction partie entière $[.]$ ( $[x]$ défini comme étant le plus grand entier inférieur ou égal au nombre réel x, nous pouvons construire plusieurs formules pour le nième nombre premier. Ces formules sont aussi basées sur le théorème de Wilson et n'ont qu'une petite valeur pratique : il existe des méthodes beaucoup plus efficientes.

Définissons

$\pi(m) = \sum_{j=2}^m \frac { \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) }$

ou, alternativement,

$\pi(m) = \sum_{j=2}^m \left[ {(j-1)! + 1 \over j} - \left[{(j-1)! \over j}\right] \right]$

Ces définitions sont équivalentes ;π (m) est la quantité de nombres premiers inférieurs ou égaux à m. Le nième nombre premier p_n peut être écrit comme

$p_n = 1 + \sum_{m=1}^{2^n} \left[ \left[ { n \over 1 + \pi(m) } \right]^{1 \over n} \right]$

Une autre approche qui n'utilise pas de factorielles est le théorème de Wilson, mais emploie massivement la fonction partie entière (S. M. Ruiz 2000) : définissons en premier

$\pi(k) = k - 1 + \sum_{j=2}^k \left[ {2 \over j} \left(1 + \sum_{s=1}^{\left[\sqrt{j}\right]} \left(\left[{ j-1 \over s}\right] - \left[{j \over s}\right]\right) \right)\right]$