Marcel Pagnol : 28 février 1895 - 18 avril 1974. Écrivain, dramaturge, cinéaste et académicien français, on lui doit entre autre ses souvenirs d'enfance... Mais pas seulement ça ! On lui doit aussi ceci :

Si n est impair, alors n+(n+1)+n(n+1) est premier.

Pour n=1, 1+2+1×2=5 (premier)
Pour n=3, 3+4+3×4=19 (premier)
Pour n=5, 5+6+5×6=41 (premier)
etc.
Bon, évidemment, si il avait essayé n=11, il aurait vu que 11+12+11×12=155, qui n'est pas un nombre premier (Divisible par 5).

Un formule qui donnerait tous les nombres premiers, ça serait quelque chose de beau, non ?! Ca pourrait permettre d'avoir des nombres premiers aussi grands que l'on veut. Aujourd'hui, on ne connait pas de nombres premiers plus grands que 232582657+1...

Après tout, il y a bien une formule qui donne tous les nombres impairs (2n+1) ou une qui donne tous les nombres de Fibonacci (FiboFormule), alors pourquoi pas une formule qui donnerait tous les nombres premiers ?

Pagnol n'est pas le premier à s'y être cassé les dents avec sa formule (4n²+10n+5), Euler a été le premier à s'y atteler. A l'époque, il a trouvé la formule n² − n + 41... (Qui, évidemment, ne marche pas pour n=41, car le résultat sera divisible par 41). On a fini par démontrer qu'on ne pouvait pas trouver de polynôme a une seule variable donnant tous les nombres premiers.

Si cette formule existait, ça se saurait : on l'aurait depuis longtemps utilisé pour battre ce misérable record du nombre premier le plus grand (9 808 358 chiffres).

Et pourtant ! Il y a bien un polynôme qui donne la totalité des nombres premiers. On doit cette formule à Jones, Sato, Wada et Wiens en 1976. Voici la formule :

Jones

C'est vrai, on a déjà vu des formules plus simples, mais celle-ci fonctionne, elle peut donner tous les nombres premiers, pourvu que le résultat est positif. C'est simplement un polynôme de degré 25 avec 26 variables.

Evidemment, il y a un hic, quand on regarde de plus près la formule. Il s'agit du produit de deux membres : d'un côté, (k+2), et de l'autre, (1-plein de choses). Pour obtenir un résultat positif, il faut nécéssairement que le "plein de chose" soit nul : il s'agit finalement d'un système de 14 équations diophantiennes (à coefficients entiers) à 26 inconnues. Autant le dire simplement : c'est quasiment impossible d'avoir de solutions avec cette formule. A l'heure d'aujourd'hui, on a juste réussit à obtenir 2...

Mais ce n'est pas grave ! Lâchons les polynomes (même s'il y en a d'autres du même genre, dont un avec 10 variables, de de degré 1045) et cherchons une autre formule qui pourrait donner tous les nombres premiers.

Grace au théorème de Wilson (une histoire de congruence sur les nombres premiers), on a pu trouver une très chouette formule, qui donne tous les nombres premiers dans l'ordre :

Wilson1
(Les drôles de traits verticaux, c'est la fonction partie entière)

Sinon, si vous n'aimez pas les sinus et les factoriels, il y a aussi cette charmante formule plutôt basée sur les parties entières...

Wilson

En fait, ces deux formules sont aussi inutilisables que la formule de Jones, Sato, Wada et Wiens, on a plus vite fait de prendre des nombres au hasard et de tester leur primalité par des algorithmes simples.

Tous ça pour dire que l'on cherche encore la formule miracle...
Si elle existe...


Sources :
Fortement inspiré de wikipédia
(Et un peu d'une conférence donnée à la fac sur le sujet)