Une formule pour les nombres premiers ?

Comprendre la distribution des nombres premiers a été un défi pour les mathématiciens de tous les temps. Certains de ceux partis dans la quête du Graal ont cherché à les décrire à l’aide des formules mathématiques explicites. Il s’avère que toutes les formules construites à ce propos n’ont pas été d’une grande utilité, car travailler avec ces formules est souvent plus compliqué que de tester directement les nombres premiers…

Récemment, Eric Rowland un jeune étudiant en thèse de Doron Zeilberger a fait une découverte étonnante dans cette direction.

On définit la suite d’entiers qui commence par [ a_1=7, ] et dont chaque terme s’obtient du précedent par la récurrence : [ a_n=a_n-1+gcd(n, a_n-1),] où gcd(a,b) signifie le plus grand diviseur commun des nombres a et b.

Considèrons ensuite les différences des termes consécutifs, c’est-à-dire la suite [ a_2-a_1, a_3-a_2, …, a_n-a_n-1, … ] dont les premiers termes sont [ 1,1,1,5,3, 1,1,1,1,11,3,1,1,1,1,1,1,1,1,1,1,23,3,1,…]

On ne voit apparaître que des 1 et des nombres premiers.

Et en effet, en 2008 Rowland a démontré, que chaque terme de cette suite est soit 1 soit un nombre premier !

Cette jolie découverte a été publiée dans Journal of Integer Sequences en 2008, avec une présentation par Jeffrey Shalit, éditeur de cette publication, que l’on peut trouver sur son blog : Recursivity

Les applications de cette formule à la construction des grands nombres premiers sont assez limitées car on peut prouver qu’il faut attendre « longtemps » avant de rencontrer le nombre premier p, le nombre de pas de récurrence nécessaires étant du même ordre de grandeur que p.

Cependant la simplicité de cette formule de récurrence, en contraste avec la complexité de la suite des nombres premiers, fait rêver l’amateur d’énigmes mathématiques…