Formules pour les nombres premiers

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, la recherche de formules exactes donnant tous les nombres premiers (ou même donnant uniquement certains des nombres premiers) s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées. Cette page recense les différents résultats obtenus.

Formules exactes simples[modifier | modifier le code]

Le rêve d'une formule exacte et simple donnant le ne nombre premier pn, ou le nombre π(n) de nombres premiers inférieurs ou égaux à n, s'est très tôt heurté à l'extrême irrégularité de leur répartition, ce qui a amené à se contenter d'objectifs moins ambitieux. Mais même la recherche de formules ne donnant que des nombres premiers s'avère assez décevante ; ainsi, il est facile de montrer qu'il n'existe aucune fonction polynôme non constante P(n) qui ne prendrait que des valeurs premières pour tous les entiers n, ou même pour presque tous les n ; en fait, on ignore même s'il existe un polynôme de degré > 1 qui prenne une infinité de valeurs premières[1].

C'est ce qui explique l'intérêt de la remarque d'Euler : le polynôme quadratique P(n) = n2 + n + 41 est premier pour tous les nombres entiers positifs strictement inférieurs à 40 (bien sûr, si n est un multiple de 41, P(n) sera lui aussi un multiple de 41, et donc non premier). D'ailleurs, 41 est le plus grand « nombre chanceux d'Euler », c'est-à-dire le plus grand entier A pour lequel le polynôme n2 + n + A est premier pour tous les n strictement inférieurs à A – 1 ; cela résulte du théorème de Stark-Heegner, un résultat de la théorie des corps de classes qui n'a été démontré qu'en 1967.

D'autres formules utilisant des fonctions plus générales, telle celle de Mersenne, avaient été envisagées, la plus célèbre étant celle conjecturée par Fermat : Fn = 22n + 1 est premier pour tout n. Hélas, si ces nombres (appelés désormais nombres de Fermat) sont bien premiers pour 0 ≤ n ≤ 4, Euler découvrit que le sixième, F5, est divisible par 641, ruinant la conjecture ; actuellement, on pense au contraire que Fn est toujours composé dès que n > 4 et, dans le même genre, on ne connait que la formule théorique de Mills pour ne donner que des nombres premiers… si ce n'est que, justement, elle est purement théorique, comme on le verra dans la dernière section.

Formules approchées[modifier | modifier le code]

Des formules approchées donnant pn ou π(n) ont été imaginées au XVIIIe siècle, culminant avec les conjectures de Legendre et Gauss. Si leur hypothèse la plus simple, \scriptstyle\lim_{n\to+\infty}\pi(n)\ln n/n=1, a été démontré par Hadamard et La Vallée Poussin un siècle plus tard (c'est le théorème des nombres premiers), la difficulté du problème est bien montrée par le fait qu'une des conjectures de Gauss, plus précise, et majorant π(n) par \scriptstyle{\rm Li}(n)=\int_2^n\frac{\mathrm dx}{\ln x}, qui paraissait fort plausible au vu des tables de ces deux fonctions, s'est cependant révélée fausse, mais seulement pour des valeurs de n gigantesques[2].

Des résultats plus précis, et en particulier une bonne estimation du terme d'erreur h(n) dans la formule pn = n ln n + h(n), font encore l'objet de conjectures (dépendant souvent de l'hypothèse de Riemann) ; parmi les meilleurs résultats vraiment démontrés, on peut citer l'encadrement suivant, déterminé par Dusart en 1999[3] :

n\Big(\ln n + \ln \ln n -1\Big) < p_n<n\Big(\ln n + \ln \ln n -1/2\Big) .

Ces méthodes sont loin de donner des formules exactes ; par exemple, cet encadrement affirme seulement que le millième nombre premier, 7919, est compris entre 7840 et 8341.

Formules exactes sans intérêt pratique[modifier | modifier le code]

Malgré les remarques précédentes, il est cependant possible d'obtenir des formules exactes d'apparence simple, mais sans intérêt pratique du fait de calculs trop longs.

Utilisation du théorème de Wilson[modifier | modifier le code]

Le théorème de Wilson permet facilement de montrer que la fonction f(n) = 2 + (2(n!) mod(n + 1)) produit tous les nombres premiers, et seulement eux, quand n parcourt tous les entiers positifs : f(n) = n + 1 si n + 1 est premier, et f(n) = 2 sinon[4].

Le recours à la fonction modulo n'est pas gênant, car on sait la calculer rapidement ; en revanche, la factorielle de n prend rapidement des valeurs bien trop grandes pour être utilisables en pratique ; de plus, cette fonction ne donne pas réellement π(n), mais teste seulement si n est premier ou non, et même s'il existe des moyens de ne calculer f(n) qu'en utilisant des entiers inférieurs à n, il faut cependant environ n opérations élémentaires pour le faire, elle est donc, pour calculer π(n), beaucoup plus inefficace que la méthode de division par tous les entiers inférieurs ou égaux à n, elle-même bien moins rapide que les meilleurs tests de primalité actuellement connus.

D'autres formules donnant directement pn ou π(n) peuvent être construites à partir de f ; ainsi, on a, en utilisant la fonction partie entière [ ∙ ] :

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

mais ces formules sont, bien évidemment, encore moins utilisables que celle donnant f.

Simulation du crible d'Ératosthène[modifier | modifier le code]

Une autre approche, plus prometteuse et n'utilisant pas le théorème de Wilson, consiste essentiellement à simuler le crible d'Ératosthène, ou les formules qu'on peut en déduire, comme la formule d'inclusion-exclusion de Legendre[5] ; c'est le terrain de prédilection de nombreux amateurs, ainsi, les formules suivantes ont été déterminées en 2000 par un enseignant espagnol, S. M. Ruiz[6]  :

\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]

et

p_n = 1 + \sum_{k=1}^{2([ n \ln(n)]+1)} \left(1 - \left[{\pi(k) \over n} \right]\right).

On remarquera le nombre important de sommations dans ces formules, qui fait qu'elles seraient, elles aussi, peu utilisables en pratique ; de bien meilleures méthodes de calcul exact de π(n) et pn, qu'on trouvera détaillées dans l'article consacré à ces fonctions, restent d'ailleurs relativement inefficaces[7].

Relation diophantienne[modifier | modifier le code]

Compte tenu des remarques de la première section, l'existence de polynômes à plusieurs variables ne prenant que des valeurs premières paraissait peu vraisemblable. Aussi, les travaux de Matiyasevich qui a résolu en 1970 le dixième problème de Hilbert en montrant que toute relation diophantienne pouvait être codée par un tel polynôme, provoquèrent une véritable surprise. Il est même possible de donner des exemples explicites de ce résultat ; ainsi, le monstrueux polynôme suivant (de degré 25, et comportant 26 variables) :

(k+2){1 – (wz+h+j–q)2 – [(gk+2g+k+1)(h+j) + h – z]2 – (2n+p+q+z–e)2 – [16(k+1)3(k+2)(n+1)2 + 1 – f2]2 – [e3(e+2)(a+1)2 + 1 – o2]2 – [(a2–1)y2 + 1 – x2]2 – [16r2y4(a2–1) + 1 – u2]2
– [((a+u2(u2–a))2–1)(n+4dy)2 + 1 – (x+cu)2]2 – [n+l+v–y]2– [(a2–1)l2 + 1 – m2]2 – [ai+k+1–l–i]2 – [p + l(a–n–1) + b(2an+2a–n2–2n–2) – m]2 – [q+ y(a–p–1) + s(2ap + 2a – p2 – 2p – 2) – x]2
– [z + pl(a–p) + t(2ap – p2 – 1) – pm]2}

a, pour ensemble de valeurs positives, exactement l'ensemble des nombres premiers[8].

On peut cependant se demander s'il s'agit bien là encore d'une « formule ». En effet, il n'existe actuellement aucune valeur connue des paramètres (a,b,c ... z) produisant une valeur positive du polynôme[réf. nécessaire], qui ne peut donc pas être utilisé pour générer des nombres premiers : ce polynôme de la forme (k+2){1 – 14 expressions élevées au carré} ne donne une valeur positive que si les 14 équations diophantiennes correspondant aux expressions sont simultanément nulles. Or il n'existe aucune méthode connue pour résoudre un tel système autrement que par l'exploration de toutes les combinaisons possibles des paramètres.

Algorithme FRACTRAN[modifier | modifier le code]

Dans un ordre d'idées assez proche, Conway a défini une généralisation du problème de Syracuse, qui le transforme en un langage de programmation, FRACTRAN ; le texte suivant  :

\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}.

correspond, pour ce langage, à un programme qui produit, dans l'ordre, la suite des nombres premiers, ce qui peut être considéré comme une formule au moins aussi élégante que celles qui précédent.

Formule de Mills[modifier | modifier le code]

Enfin, Mills a montré qu'il existe des nombres réels M tels que pour tout entier n, la partie entière de M(3n) soit un nombre premier. Le plus petit M ayant cette propriété, la constante de Mills, est d'ailleurs connu avec une bonne précision, mais qui s'avèrerait tout aussi illusoire pour calculer réellement de grands nombres premiers, ne serait-ce que parce que la taille de p(n) = [M(3n)] devient rapidement bien supérieure à tout ce qu'un ordinateur peut contenir (pour stocker p(25), on a déjà besoin d'un téraoctet).

Notes et références[modifier | modifier le code]

  1. (en) Andrew Granville, Conférence à la MAA, décembre 2008, d'où sont tirées beaucoup des remarques informelles de cet article ; en voici l'enregistrement (audio).
  2. Voir Nombre de Skewes, où l'on trouvera aussi les meilleures valeurs de ces n actuellement connues.
  3. (en) Pierre Dusart, « The kth prime is greater than k(ln k + ln ln k-1) for k≥2 », Mathematics of Computation, vol. 68,‎ 1999, p. 411–415 (lire en ligne) ; en fait, cet article donne des bornes un peu plus précises, mais valables seulement pour n assez grand : on a (pour n > 40 000)
    n(\ln n + \ln \ln n -1)<p_n<n(\ln n + \ln \ln n -0,95).
  4. En effet, si n + 1 est premier, d'après le théorème de Wilson, on a n! congru à -1 modulo n + 1, donc la division de 2(n!) par n + 1 laisse un reste de n – 1 et f(n) = 2 + (n – 1) = n + 1 dans ce cas ; si n + 1 est composé et strictement supérieur à 4, n! est divisible par n + 1 et f(n) = 2 + 0 = 2 ; enfin, f(0) = 2 et f(3) = 2.
  5. Cette formule (connue aussi sous le nom de formule du crible) a été déterminée par Legendre pour calculer rapidement π(n) sans avoir besoin de chercher explicitement tous les nombres premiers inférieurs à n ; on la trouvera, ainsi que ses améliorations plus récentes, dans l'article consacré à π(n).
  6. Ces formules figurent sur la page personnelle de leur auteur, Sebastián Martín Ruiz (es) ; il en a publié une démonstration en 2002 (en), en collaboration avec S. Sondow.
  7. Ainsi, on n'est actuellement capable de déterminer exactement que π(1023), alors qu'on sait tester si un nombre de l'ordre de 10200 est premier en quelques minutes.
  8. (en) James P. Jones, Daihachiro Sato (en), Hideo Wada et Douglas Wiens (en), « Diophantine representation of the set of prime numbers », Amer. Math. Monthly, vol. 83, no 6,‎ 1976, p. 449–464 (lire en ligne).

Voir aussi[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Prime Formulas », MathWorld