Voir la source de Formules pour les nombres premiers

En [[mathématiques]], la recherche de '''[[Formule (mathématiques)|formules]]''' exactes donnant tous '''les [[Nombre premier|nombres premiers]]''', certaines familles de nombres premiers ou le {{Nobr|''n''-ième}} nombre premier s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées. Cette page recense les principaux résultats obtenus.

== Formules exactes simples ==
L'espoir d'obtenir une formule exacte et simple donnant le ''n''-ième nombre premier {{mvar|p{{ind|n}}}}, ou le [[Fonction de compte des nombres premiers|nombre {{math|π(''n'')}} de nombres premiers inférieurs ou égaux à ''n'']], s'est très tôt heurté à l'extrême irrégularité de [[Nombre premier#Répartition des nombres premiers|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 polynomiale]] non constante {{math|''P''(''n'')}} qui ne prendrait que des valeurs premières pour tous les entiers {{mvar|n}}, ou même pour [[Sous-ensemble cofini|presque tous]] les {{mvar|n}}<ref>{{Ouvrage |langue originale=en |auteur1=[[Godfrey Harold Hardy|G. H. Hardy]] |auteur2=[[Edward Maitland Wright|E. M. Wright]] |traducteur=F. Sauvageot |titre=Introduction à la théorie des nombres |titre original=[[Modèle:HardyWright|An Introduction to the Theory of Numbers]] |éditeur=[[Vuibert]]-[[Springer Verlag|Springer]] |année=2007 |passage=23 }}, th. 21, dû à [[Christian Goldbach|Goldbach]] (''[http://eulerarchive.maa.org/correspondence/letters/OO0878.pdf Lettre CLI]'', à [[Leonhard Euler|Euler]], 18 novembre 1752). Pour une généralisation, voir aussi le théorème 22, p. 24 et 83, dû à {{Article|lang=en|auteur={{Lien|Morgan Ward}}|titre=A generalization of a familiar theorem concerning prime numbers|revue=J. London Math. Soc.|vol=5|année=1930|p.=106-107}}.</ref> ; en fait, on ignore même s'il existe un polynôme de degré > 1 qui prenne une infinité de valeurs premières<ref>{{en}} [[Andrew Granville]], [http://www.maa.org/news/121508granville.html Conférence à la MAA, décembre 2008], d'où sont tirées beaucoup des remarques informelles de cet article ; en voici [http://www.maa.org/audio%20clips/ag/Granville%20whole.MP3 l'enregistrement (audio)] ; il est cependant conjecturé que, par exemple, c'est le cas du polynôme {{math|''n''{{2}} + 1}}, et la [[conjecture de Bateman-Horn]] prédit le comportement de ces valeurs premières de manière bien confirmée empiriquement. </ref>.

C'est ce qui explique l'intérêt de la remarque d'[[Leonhard Euler|Euler]] : le [[Fonction du second degré|polynôme quadratique]] {{math|''P''(''n'') {{=}} ''n''{{2}} + ''n'' + 41}} est premier pour tous les nombres [[Entier naturel|entiers positifs]] strictement inférieurs à 40 (<math>P(40)= 1681 = 41^2</math> et si {{mvar|n}} est un multiple de 41, {{math|''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 {{mvar|A}} pour lequel le polynôme {{math|''n''{{2}} + ''n'' + ''A''}} est premier pour tous les {{mvar|n}} strictement inférieurs à {{math|''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. De manière similaire, d'autres formules polynomiales (de degré plus élevé) produisent des suites de nombres premiers. Ainsi, en 2010, l'une d'entre elles a permis d'établir un nouveau record : une suite de 58 nombres premiers<ref>{{Lien web
 |auteur      =David Larousserie
 |titre       = Nouvelle suite record pour les nombres premiers
 |url         = https://www.sciencesetavenir.fr/fondamental/nouvelle-suite-record-pour-les-nombres-premiers_22615
 |site        = [[Sciences et Avenir]]
 |date        = 23 septembre 2010
 |consulté le = 4 mai 2018 }}.</ref> :

:<math>\frac1{72}n^6 - \frac5{24}n^5 - \frac{1493}{72}n^4 + \frac{1027}8n^3 + \frac{100471}{18}n^2 - \frac{11971}6n - 57347</math> est premier<ref>Il s'agit en fait de nombres premiers dans '''Z''', c'est-à-dire d'entiers relatifs dont la valeur absolue est un nombre premier.</ref> pour chaque entier {{mvar|n}} de –42 à 15.

D'autres formules utilisant des fonctions plus générales, telle celle de [[Marin Mersenne|Mersenne]], avaient été envisagées, la plus célèbre étant celle conjecturée par [[Pierre de Fermat|Fermat]] : {{math|''F{{ind|n}}'' {{=}} 2{{exp|2{{exp|''n''}}}} + 1}} est premier pour tout {{mvar|n}}. Hélas, si ces nombres (appelés désormais [[Nombre de Fermat|nombres de Fermat]]) sont bien premiers pour {{math|0 ≤ ''n'' ≤ 4}}, Euler découvrit que le sixième, {{math|''F''{{ind|5}}}}, est divisible par 641, ruinant la conjecture ; actuellement, on pense au contraire que {{mvar|F{{ind|n}}}} est toujours [[Nombre composé|composé]] dès que {{math|''n'' > 4}}<ref>Boklan et [[John H. Conway|Conway]] ont publié en mai 2016 une analyse très fine estimant la probabilité d'un autre nombre premier à moins d'un sur un milliard ({{Article | langue = en | auteur1 = Boklan | prénom1 = Kent D. | auteur2 = Conway | prénom2 = John H.  | titre = Expect at most one billionth of a new Fermat Prime! | périodique = Mathematical Intelligencer. | éditeur = Springer | année = 2016 | ean = <!-- code EAN de la revue si elle n'a pas ISBN ou ISSN --> | consulté le = 8 mai 2016 | arxiv = 1605.01371v1 }}).</ref>. Dans le même genre, la [[constante de Mills|formule de Mills]] n'engendre que des nombres premiers, mais a l'inconvénient de n'être que théorique.

== Formules approchées ==
{{article détaillé|Fonction de compte des nombres premiers}}

Des formules approchées donnant {{mvar|p{{ind|n}}}} ou {{math|π(''n'')}} ont été imaginées au {{s-|XVIII}}, culminant avec les conjectures de [[Adrien-Marie Legendre|Legendre]] et [[Carl Friedrich Gauss|Gauss]]. Si leur hypothèse la plus simple, <math>\lim_{n\to+\infty}\pi(n)\ln n/n=1,</math> a été démontrée par [[Jacques Hadamard|Hadamard]] et [[Charles-Jean de La Vallée Poussin|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 {{math|π(''n'')}} par <math>{\rm Li}(n)=\int_2^n\frac{\mathrm dx}{\ln x}</math>, qui paraissait fort plausible au vu des [[Théorème des nombres premiers#Exemples d'estimations numériques|tables de ces deux fonctions]], s'est cependant révélée fausse, mais seulement pour des valeurs de {{mvar|n}} gigantesques<ref>Voir [[Nombre de Skewes]], où l'on trouvera aussi les meilleures valeurs de ces ''n'' actuellement connues.</ref>.

Des résultats plus précis, et en particulier une bonne estimation du terme d'erreur {{math|''h''(''n'')}} dans la formule {{math|''p{{ind|n}}'' {{=}} ''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<ref>{{article |langue=en |auteur=Pierre Dusart|titre=The ''k''th prime is greater than ''k(ln k + ln ln k-1)'' for ''k''≥2 |journal=Mathematics of Computation |volume=68 |année=1999 |url=http://www.ams.org/mcom/1999-68-225/S0025-5718-99-01037-6/S0025-5718-99-01037-6.pdf |pages=411–415 }} ; l'encadrement est valable pour ''n'' > 4 avec la convention <math>p_2=2</math> et en fait, cet article donne des bornes un peu plus précises, mais valables seulement pour {{mvar|n}} assez grand : on a (pour {{math|''n'' > 40000}}) <math>n(\ln n + \ln \ln n -1)<p_n<n(\ln n + \ln \ln n -0,95) ;</math> pour le cent millième nombre premier, <math>p_{100000}=1\,299\,709</math>, cela correspond à l'encadrement <math>1\,295\,639<p_{100000}<1\,300\,639</math>.</ref> :
<center><math>n\left(\ln n + \ln \ln n -1\right) < p_n<n\left(\ln n + \ln \ln n -1/2\right) .</math></center>

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 ==
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 ===
Le [[théorème de Wilson]] permet facilement de montrer que la fonction {{math|''f''(''n'') {{=}} 2 + (2(''n''!) mod(''n'' + 1))}} produit tous les nombres premiers, et seulement eux, quand {{mvar|n}} parcourt tous les entiers positifs : {{math|1=''f''(''n'') = ''n'' + 1}} si ''n'' + 1 est premier, et {{math|''f''(''n'') {{=}} 2}} sinon<ref>En effet, si ''n'' + 1 est premier, d'après le théorème de Wilson, on a {{math|''n''!}} congru à –1 modulo {{math|''n'' + 1}}, donc la division de {{math|2(''n''!)}} par {{math|''n'' + 1}} laisse un reste de ''n'' – 1 et ''f''(''n'') = 2 + (''n'' – 1) = ''n'' + 1 dans ce cas ; [[Théorème de Wilson#Démonstrations|si ''n'' + 1 est composé et strictement supérieur à 4, ''n''! est divisible par ''n'' + 1]] et {{math|''f''(''n'') {{=}} 2 + 0 {{=}} 2}} ; enfin, {{math|''f''(0) {{=}} 2}} et {{math|''f''(3) {{=}} 2}}.</ref>. 

La [[factorielle]] de {{mvar|n}} prend rapidement des valeurs bien trop grandes pour être utilisable en pratique, mais le recours à la [[Modulo_(informatique)|fonction modulo]] (que l'on sait calculer rapidement) contourne cette difficulté ; cependant, les seules méthodes  connues pour calculer {{math|''f''(''n'')}} prennent environ {{mvar|n}} [[Opération élémentaire|opérations élémentaires]], de plus, cette fonction ne donne pas réellement {{math|π(''n'')}}, mais teste seulement si {{mvar|n}} est premier ou non ;  pour ce test, ou pour calculer {{math|π(''n'')}}, {{mvar|f}} est donc beaucoup plus inefficace que la méthode  de division par tous les entiers inférieurs ou égaux à {{sqrt|''n''}} (ou que le [[crible d'Ératosthène]]), méthodes elles-mêmes bien moins rapides que les meilleurs [[test de primalité|tests de primalité]] actuellement connus.

D'autres formules donnant directement {{mvar|p{{ind|n}}}} ou {{math|π(''n'')}} peuvent être construites à partir de {{mvar|f}} ; ainsi, on a, en utilisant la [[partie entière|fonction partie entière]] {{math|⌊∙⌋}} :
:<math> \pi(n) = \sum_{j=2}^n \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor</math> ; 

mais ces formules sont encore moins facilement utilisables que celle donnant {{mvar|f}}.

=== Simulation du crible d'Ératosthène ===
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 [[Principe d'inclusion-exclusion|formule d'inclusion-exclusion]] de Legendre<ref>Cette formule (connue aussi sous le nom de '''formule du crible''') a été déterminée par Legendre pour calculer rapidement {{math|π(''n'')}} sans avoir besoin de chercher explicitement tous les  nombres premiers inférieurs à {{mvar|n}} ; on la trouvera, ainsi que ses améliorations plus récentes, dans [[Fonction de compte des nombres premiers#Algorithmes d'évaluation de π(x)|l'article consacré à {{math|π(''n'')}}]].</ref> ; 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<ref>Ces formules figurent sur la [http://perso.wanadoo.es/smaranda/ page personnelle de leur auteur, Sebastián Martín Ruiz] {{es}} ; il en a publié [https://arxiv.org/abs/math/0210312  une démonstration en 2002] {{en}}, en collaboration avec S. Sondow.</ref>   : 
:<math>\pi(n) = n - 1 + \sum_{j=2}^n \left[ {2 \over j} \left(1 +  \sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j-1 \over s}\right\rfloor - \left\lfloor{j \over s}\right\rfloor\right) \right)\right] </math>                 
et
:<math>p_n = 1 + \sum_{k=1}^{2(\lfloor n \ln(n)\rfloor+1)} \left(1 - \left\lfloor{\pi(k) \over n} \right\rfloor\right). </math> 

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 {{math|π(''n'')}} et {{mvar|p{{ind|n}}}}, qu'on trouvera détaillées dans [[Fonction de compte des nombres premiers#Algorithmes d'évaluation de π(x)|l'article consacré à ces fonctions]], restent d'ailleurs relativement inefficaces{{note|texte=Ainsi, on n'est en 2016 capable de déterminer exactement que {{math|π(10{{24}})}}<ref name=conditionalcalculationofpi>{{en}} [http://primes.utm.edu/notes/pi(10%5E24).html primes.utm.edu] Conditional Calculation of pi(10^24).</ref>, alors qu'on sait tester si un nombre de l'ordre de 10{{exp|200}} est premier en quelques minutes.}}.

=== Relation diophantienne ===
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 [[Youri Matiiassevitch]], qui a résolu en [[1970]] le [[dixième problème de Hilbert]] en montrant que toute [[Diophantien#Ensemble diophantien|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)<ref>Matiiassevitch a montré en 1999 qu'on peut ramener tout polynôme codant ainsi une relation diophantienne à un polynôme en 9 variables, mais au prix, dans cet exemple, d'un degré dépassant 10<sup>45</sup>. Inversement, on a déterminé un polynôme de degré 4, mais à 56 variables ; voir à ce sujet {{article |langue=en |doi=10.2307/2273588 |prénom1=James P. |nom1=Jones |année=1982 |titre=Universal diophantine equation |périodique=[[Liste des journaux scientifiques en mathématiques#J|J. Symb. Logic]]|volume=47 |numéro=3 |pages=549–571}}.</ref> :

:<math> (k+2)(1-\alpha_0^2-\alpha_1^2-\cdots-\alpha_{13}^2)</math>
avec
:<math>\alpha_0=wz+h+j-q</math>
:<math>\alpha_1=(gk+2g+k+1)(h+j) + h - z</math>
:<math>\alpha_2=16(k+1)^3(k+2)(n+1)^2 + 1 - f^2</math>
:<math>\alpha_3=2n+p+q+z-e</math>
:<math>\alpha_4=e^3(e + 2)(a + 1)^2 + 1 - o^2</math>
:<math>\alpha_5=(a^2-1)y^2 + 1 - x^2</math>
:<math>\alpha_6=16r^2y^4(a^2-1) + 1 - u^2</math>
:<math>\alpha_7=n+l+v-y</math>
:<math>\alpha_8=(a^2-1)l^2 + 1 - m^2</math>
:<math>\alpha_9=ai+k+1-l-i</math>
:<math>\alpha_{10}=[(a + u^2(u^2-a))^2 - 1](n + 4dy)^2 + 1 - (x+cu)^2</math>
:<math>\alpha_{11}=p + l(a-n-1) + b(2an+2a-n^2-2n-2) - m</math>
:<math>\alpha_{12}=q + y(a-p-1) + s(2ap+2a-p^2-2p-2) - x</math>
:<math>\alpha_{13}=z + pl(a-p) + t(2ap-p^2-1) - pm</math>

a, pour ensemble de valeurs ''strictement positives'' (lorsque <math>(a,\dots,z)\in\N^{26}</math>), exactement l'ensemble des nombres premiers<ref>{{article|lang=en|prénom1=James P.|nom1=Jones|auteur2={{Lien|Daihachiro Sato}}|auteur3=Hideo Wada|auteur4=[[Douglas Wiens]]|url=http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/JonesSatoWadaWiens.pdf|année=1976|titre=Diophantine representation of the set of prime numbers|revue=[[American Mathematical Monthly|Amer. Math. Monthly]]|vol=83|p.=449-464|numéro=6}} ([[Prix Lester Randolph Ford]] 1977).</ref>.

Mais on peut cependant se demander s'il s'agit bien là encore d'une « formule ». Il est d'ailleurs extrêmement difficile de trouver un jeu de 26 variables donnant un nombre positif, et 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.

=== Suites définies par récurrence ===
Bien qu'on ne puisse pas parler exactement de formule, une suite définie par une relation de la forme {{math|''u''{{ind|''n''+1}} {{=}} ''f''(''u{{ind|n}}'')}}, où {{mvar|f}} est une fonction assez simple, et qui ne prendrait que des valeurs premières, resterait intéressante. Certaines suites dérivées de la [[théorème d'Euclide sur les nombres premiers|démonstration d'Euclide de l'infinité des nombres premiers]] (comme la [[suite de Sylvester]]) s'avèrent décevantes à cet égard, ainsi on ne sait même pas s'il existe une infinité de [[nombre premier primoriel|nombres premiers primoriels]].  On ne connaît en fait que peu d'exemples intéressants de telles suites, d'ailleurs d'une forme un peu plus complexe.

==== Algorithme FRACTRAN ====
[[John Horton Conway|Conway]] a ainsi défini une généralisation du [[problème de Syracuse]], qui le transforme en un [[langage de programmation]], [[FRACTRAN]] ;  le texte suivant<ref>{{ouvrage|titre=The book of numbers|auteur1=John H. Conway|auteur2=Richard K. Guy|éditeur=Copernicus|page=147|année=1995|isbn=0-387-97993-X}}</ref> : <center> <math>\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}.</math></center>
correspond, pour ce langage, à un programme qui produit, dans l'ordre, la suite des nombres premiers (on peut donc l'interpréter comme une [[suite définie par récurrence]]). Pour cela, partant du nombre 2, on multiplie itérativement par la première fraction donnant un produit entier. Parmi la [[suite d'entiers]] qu'on obtiendra, les [[Puissance de deux|puissances de 2]] successives auront pour exposant la suite des nombres premiers. L'efficacité de ce programme étant extrêmement faible, l'intérêt est seulement dans l'élégance de son écriture.

==== Suite de Rowland ====
La suite {{mvar|u{{ind|n}}}} définie par la relation de récurrence
:<math> a_n = a_{n-1} + \operatorname{gcd}(n,a_{n-1}), \quad a_1 = 7, </math>
(où {{math|gcd(''x'', ''y'')}} désigne le [[PGCD]] de {{mvar|x}} et {{mvar|y}}) et {{math|''u''{{ind|''n''}} {{=}} ''a''{{ind|''n''+1}} – ''a{{ind|n}}''}} commence par  1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, ... ({{OEIS|id=A132199}}). Rowland a démontré en 2008 que cette suite ne contient (à part 1) que des nombres premiers<ref>{{Ouvrage |langue=en |prénom1=Eric S. |nom1=Rowland |titre=A Natural Prime-Generating Recurrence |volume=11 |éditeur=Journal of Integer Sequences |année=2008 |pages totales=08.2.8 |bibcode=2008JIntS..11...28R |arxiv=0710.3217 |lire en ligne=http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.html}}</ref>.

==== Suites dépendant d'un nombre réel ====
===== Formule de Mills =====
En 1947, William H. Mills a montré qu'il existe des nombres réels {{mvar|M}} tels que pour tout entier {{mvar|n}}, la partie entière de {{math|''M''{{exp|(3{{exp|''n''}})}}}} est un nombre premier<ref>{{Article|lang=en|titre=A prime-representing function|auteur=William H. Mills|revue=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]]|année=1947|p.=604 et 1196|url=http://www.ams.org/journals/bull/1947-53-06/S0002-9904-1947-08849-2}}.</ref>. Le plus petit {{mvar|M}} ayant cette propriété, la [[constante de Mills]], est d'ailleurs connu avec une bonne précision, mais qui s'avère tout aussi illusoire pour calculer de grands nombres premiers, par exemple parce que la taille de {{math|''p''(''n'') {{=}} ⌊''M''{{exp|(3{{exp|''n''}})}}⌋}} devient rapidement bien supérieure à tout ce qu'un ordinateur peut contenir (pour stocker {{math|''p''(25)}}, on a déjà besoin d'un [[Octet#Multiples normalisés|téraoctet]]).

===== Suite de Fridman =====
En 2017, Fridman {{et al.}} ont démontré<ref name=AMM126-1>{{article|lang=en|auteur=D. Fridman|auteur2=J. Garbulsky|auteur3=B. Glecer|auteur4=J. Grime|auteur5=M. T. Florentin|titre=A prime-representing constant|périodique=[[The American Mathematical Monthly|Amer. Math. Month.]]|volume=126|numéro=1|date=janvier 2019|pages=70-72|url=https://www.researchgate.net/publication/330746181_A_Prime-Representing_Constant|doi=10.1080/00029890.2019.1530554}}.</ref> que la suite de [[Nombre réel|réels]] {{math|(''f{{ind|n}}'')}} définie par :
*<math>f_1=\sum_{k=1}^\infty \frac{p_k-1}{p_{k-1}\#}=\sum_{k=1}^\infty \frac{p_k-1}{\prod_{i=1}^{k-1} p_i}</math>
*<math>\forall n\ge1\quad f_{n+1}=\lfloor f_n\rfloor\left(f_n-\lfloor f_n\rfloor+1\right)</math>
vérifie : 
:<math>\forall n\ge1\quad p_n=\lfloor f_n\rfloor</math>.
L'[[Nombre irrationnel|irrationnel]] {{math|1=''f''{{ind|1}} = 2,9200509773…}}<ref>Suite {{OEIS2C|A249270}} de l'[[OEIS]].</ref> n'est autre<ref>{{Ouvrage |langue=en |auteur1=Steven R. Finch |titre=Mathematical Constants |volume=II |éditeur=Cambridge University Press |année=2018 |passage=171 |lire en ligne={{Google Livres|z2R9DwAAQBAJ|page=171}}}}.</ref> que la [[Lemme de Cesàro|valeur moyenne de la suite]] 2, 3, 2, 3, 2, 5, etc. dont le {{mvar|n}}-ième terme est le plus petit nombre premier ne divisant pas {{mvar|n}}<ref name=AMM126-1/>{{,}}<ref>Suite {{OEIS2C|A053669}} de l'OEIS : {{Citation étrangère|lang=en|Smallest prime not dividing n}}.</ref>.

Bien que les calculs correspondants soient plus maniables que ceux de la formule de Mills, ce résultat reste tout aussi théorique. En effet, ces calculs nécessitent de connaître un nombre de plus en plus important de décimales de {{math|''f''{{ind|1}}}} {{refsou|date=mars 2019|(environ {{mvar|n}} décimales pour obtenir {{mvar|p{{ind|n}}}})}}, mais {{refsou|date=mars 2019|pour obtenir {{mvar|n}} décimales de {{math|''f''{{ind|1}}}}, il faut déjà connaître les valeurs des {{mvar|n}} premiers nombres premiers}}. Par contre, cela procure une compression ''mémoire'', en effet, le stockage de <math>n</math> décimales nécessite moins de mémoire que pour les <math>n</math> premiers nombres premiers.

===== Fraction continue =====
La notion de [[fraction continue]] permet de définir le nombre réel positif <math>u_1=[p_1,p_2,p_3,...]=2.31303673643...</math> {{OEIS2C|A064442}} à partir duquel on retrouve la suite des nombres premiers en utilisant la récurrence suivante: <math> u_{n+1} = (u_n - \lfloor u_n\rfloor)^{-1} </math>. Il s'ensuit que <math>p_n =  \lfloor u_n  \rfloor </math>.

La méthode de Fridman et al. peut être vue comme une alternative de la méthode par fraction continue (connue antérieurement), et on peut donc émettre la même réserve : le nombre <math> u_1 </math> est défini (ci-dessus) en utilisant les nombres premiers, il faudrait donc une définition alternative indépendante des nombres premiers pour que cette méthode soit ''utilisable''.

== Notes et références ==
{{Traduction/Référence|en|Formula for primes|304147152|type=en}}
<references />

== Voir aussi ==
=== Bibliographie ===
* {{Merveilleux nombres premiers}}
* {{Ouvrage |langue=fr |langue originale=en |auteur1=[[Marcus du Sautoy]] |titre=[[La Symphonie des nombres premiers]] |éditeur=éditions Héloïse d'Ormesson |lieu=Paris |année=2005 |pages totales=491 |isbn=2-35087-011-1}}

=== Lien externe ===
{{MathWorld|nom_url=PrimeFormulas|titre=Prime Formulas}}
{{Palette|Classes de nombres premiers}}
{{Portail|arithmétique}}

[[Catégorie:Nombre premier]]