La Conjecture de Proth-Gilbreath
Battre le record de Andrew Odlyzko G(Pi(1013))=635 (1993)
G(Pi(1014))=693 le 05/10/2025 à 20:59:18
G(Pi(2.8x1014))=788 le 08/11/2025 à 12:39:52
CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641, École polytechnique, Institut Polytechnique de Paris, CNRS, France
[Site Map, Help and Search [Plan du Site, Aide et Recherche]]
[The Y2K Bug [Le bug de l'an 2000]]
[Real Numbers don't exist in Computers and Floating Point Computations aren't safe. [Les Nombres Réels n'existent pas dans les Ordinateurs et les Calculs Flottants ne sont pas sûrs.]]
[N'oubliez pas de visiter Une Machine Virtuelle à Explorer l'Espace-Temps et au-delà où vous trouverez plus de 10.000 images et animations à la frontière de l'Art et de la Science]
(Site WWW CMAP28 : cette page a été créée le 28/09/2025 et mise à jour le 21/11/2025 11:37:24 -CET-)
[in english/en anglais]
Remarque préliminaire :
Ce qui suit résulte d'une collaboration avec Jean-Paul Delahaye professeur émérite à l'Université de Lille,
chercheur au Laboratoire Cristal de Lille et chroniqueur bien connu de Pour La Science.
Contenu :
1-Introduction :
Une conjecture est
une proposition mathématique que l'on croit être vraie mais que l'on ne peut qualifier
de théorème
tant que toute tentative de démonstration a échoué...
Le plus bel exemple récent fut la démonstration du grand théorème de Fermat par Andrew Wiles en 1994
alors qu'il résistait aux plus grands mathématiciens depuis le XVIIe siècle.
Beaucoup de conjectures importantes sont actuellement "en attente". C'est ainsi le cas de
la conjecture de Goldbach -CG-
ou encore de celle des nombres premiers jumeaux -CNPJ-.
Pour une conjecture donnée, tant qu'une démonstration correcte n'a pas été trouvée, il est possible de tenter de
l'infirmer par la mise en évidence d'un contre-exemple, lorsque cela a un sens. Cela ne serait pas le cas pour CNPJ
car en effet ne plus voir de couples de nombres premiers jumeaux ne prouverait en aucune façon qu'en poursuivant beaucoup plus longtemps cette recherche,
de nouveaux couples n'apparaitraient pas. Par contre, pour CG découvrir un nombre pair supérieur à 2 qui ne serait pas la somme de deux
nombres premiers prouverait évidemment que CG est fausse. Malheureusement, s'il en existe un, la probabilité pour qu'il nous soit accessible est
quasiment nulle (en fait, tous les nombres entiers sont énormes, voire inimaginables,
sauf évidemment les premiers : ceux que l'on utilise dans la vie courante...).
Mais même si cette recherche de contre-exemple peut parfois paraître vaine, elle peut malgé tout être utile
en nous révélant des informations pertinentes relatives à un certain sujet et c'est le cas de conjecture de Gilbreath et des nombres premiers...
2-Définition :
Il s'agit d'une conjecture énoncée en 1958 par Norman L. Gilbreath [01] mais déjà formulée en 1878 par François Proth [02].
Elle est relative aux nombre premiers et aux séquences obtenues en calculant la valeur absolue de la différence
entre chaque nombre premier et son successeur,
puis en répétant ce processus ad infinitum [03] :
2 3 5 7 11 13 17 19 23 29 31 (...)
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
1 2 2 4 2 4 2 4 6 2 (...)
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
1 0 2 2 2 2 2 2 4 (...)
\ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ / \ /
1 2 0 0 0 0 0 2 (...)
\ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ / \ /
1 2 0 0 0 0 2 (...)
\ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ / \ /
1 2 0 0 0 2 (...)
\ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ /
1 2 0 0 2 (...)
\ / \ / \ / \ / \ /
\ / \ / \ / \ / \ /
\ / \ / \ / \ / \ /
\ / \ / \ / \ / \ /
1 2 0 2 (...)
\ / \ / \ / \ /
\ / \ / \ / \ /
\ / \ / \ / \ /
\ / \ / \ / \ /
1 2 2 (...)
\ / \ / \ /
\ / \ / \ /
\ / \ / \ /
\ / \ / \ /
1 0 (...)
\ / \ /
\ / \ /
\ / \ /
\ / \ /
1 (...)
\ /
\ /
\ /
\ /
(...)
Cette conjecture qui affirme que la première valeur de chaque ligne est un 1 (à l'exception de la première ligne où il s'agit d'un 2 -le premier nombre premier-)
a été étudiée en 1993 par Andrew Odlyzko. Il avait pu alors la vérifier pour tous les nombres premiers inférieurs à 1013.
Le dimanche 05/10/2025 à 20:45 (heure de Paris, France) j'ai réussi à la vérifier jusqu'à 1014
et le mardi 07/10/2025 à 02:25 pm (East Time), Simon Plouffe (Canada) atteignait lui-aussi cette valeur confirmant en même temps la valeur maximale (693)
de la fonction G(Pi(x)) [04] avec x ∈ [2,1014]
que j'avais anticipée le 25/09/2025.
Voici quelques visualisation de ce processus
(colonne de gauche : les signes des différences, colonne du milieu : la valeur absolue des différences et colonne de droite : les différences) :
x 
= 
x 
= 
x 
= 
x 
= 
x 
= 
avec les conventions suivantes pour le coloriage des nombres sur les images de droite :
0 = cyan foncé,
-1 = orange sombre,
+1 = orange clair,
-2 = vert sombre,
+2 = vert clair,
alors que tous les autres nombres -{3,4,5,6,7,8,...}- sont gris (gris sombre et clair respectivement pour les nombres négatifs et positifs).
D'après la Conjecture de Proth-Gilbreath, dans les images du milieu, la colonne de gauche doit être cyan ('1')
à l'exception du carré situé tout en haut qui est jaune vif ('2', le premier nombre premier).
On remarquera qu'il s'agit d'un automate cellulaire binaire monodimensionnel en ce qui concerne les carrés jaunes.
3-La théorie :
Il n'est évidemment pas possible de vérifier la Conjecture de Proth-Gilbreath puisqu'il y a une infinité de nombres premiers.
Seule une démonstration peut en venir à bout, à moins de trouver un contre-exemple, c'est-à-dire une ligne ne commençant pas par un '1'
(à l'exception de la première évidemment).
Soient pn les nombres premiers :
p1=2
p2=3
p3=5
etc...
Définissons la suite dk(n) :
d0(n) = pn pour tout n tel que n > 0
dk(n) = |dk-1(n) - dk-1(n+1)| pour tout k tel que k > 0 et pour tout n tel que n > 0
Il faut donc vérifier que :
dk(1) = 1 pour tout k tel que k > 0
Mais si cela doit être vérifié de façon exhaustive, rapidement le nombre de calculs à effectuer, ainsi
que la mémoire nécessaire dépassent la capacité des ordinateurs. Fort heureusement Andrew Odlyzko remarqua que si pour un certain N il existe K tel que :
dK(1) = 1
dK(n) ∈ {0,2} pour tout n tel que 0 < n < N+1
alors :
dk(1) = 1 pour tout k tel que K-1 < k < N+K
Appelons G(N) le plus petit k (s'il existe) tel que :
dj(1) = 1, 0 < j < k+1
dk(n) ∈ {0,2} pour tout n tel que 0 < n < N+1
Un raisonnement trivial montre que G(N) existe pour tout N et que l'on peut arrêter le processus dès qu'il n'y a plus que des '0's, des '1's et des '2's sur la ligne de rang k courante.
Par exemple :
k=0 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
≠ ≠ ≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠ ≠≠
k=1 1 2 2 4 2 4 2 4 6 2 6 4 2 4 6 6 2 6 4
≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠
k=2 1 0 2 2 2 2 2 2 4 4 2 2 2 2 0 4 4 2
≠ ≠ ≠ ≠
k=3 1 2 0 0 0 0 0 2 0 2 0 0 0 2 4 0 2
≠
k=4 1 2 0 0 0 0 2 2 2 2 0 0 2 2 4 2
≠
k=5 1 2 0 0 0 2 0 0 0 2 0 2 0 2 2
==> G=5
4-Le calcul :
En 1993 Andrew Odlyzko vérifiait cela pour tous les nombres premiers inférieurs à 1013.
Le dimanche 10/08/2025, Jean-Paul Delahaye me proposait "un beau calcul", non trivial, mais semble-t-il faisable : il
s'agissait d'aller au-delà de 1013 et d'atteindre par exemple 1014...
Sur le papier, la chose est simple : il suffit de s'inspirer de l'exemple ci-dessus, mais au lieu de s'arréter à 71 il convient de dépasser 1013.
Il est évident que les ordinateurs ne peuvent ni mémoriser et ni manipuler une telle quantité de nombres.
L'idée est donc de travailler par blocs traités successivement et de tailles compatibles avec les machines utilisées. Mais ce découpage ne peut pas
se faire naïvement comme on peut le voir en decoupant l'exemple précédent en 2 blocs :
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
1 2 2 4 2 4 2 4 6 6 4 2 4 6 6 2 6 4
1 0 2 2 2 2 2 2 2 2 2 2 0 4 4 2
0 0 0 2 4 0 2
0 0 2 2 4 2
0 2 0 2 2
De toute évidence, il manque la différence 31-29. Jean-Paul Delahaye a alors suggéré que les blocs ne soient
pas disjoints, mais se recouvrent partiellement comme suit en fonction d'un G estimé (à 5 ci-dessous) :
2 3 5 7 11 13 17 19 23 29 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
1 2 2 4 2 4 2 4 6 4 2 4 6 2 6 4 2 4 6 6 2 6 4
1 0 2 2 2 2 2 2 2 2 2 4 4 2 2 2 2 0 4 4 2
1 2 0 0 0 0 0 0 0 2 0 2 0 0 0 2 4 0 2
1 2 0 0 0 0 0 2 2 2 2 0 0 2 2 4 2
1 2 0 0 0 2 0 0 0 2 0 2 0 2 2
soit :
2 3 5 7 11 13 17 19 23 29
13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
== == == == ==
1 2 2 4 2 4 2 4 6
4 2 4 6 2 6 4 2 4 6 6 2 6 4
= = = =
1 0 2 2 2 2 2 2
2 2 2 4 4 2 2 2 2 0 4 4 2
= = =
1 2 0 0 0 0 0
0 0 2 0 2 0 0 0 2 4 0 2
= =
1 2 0 0 0 0
0 2 2 2 2 0 0 2 2 4 2
=
1 2 0 0 0
2 0 0 0 2 0 2 0 2 2
On pourrait remarquer que ce recouvrement de 5 nombres augmente de façon significative le nombre de calculs. En fait c'est vrai sur cet exemple
où chaque bloc ne contient que 10 nombres. Mais les calculs qui seront faits pour battre le record de 1993 utiliseront des blocs
beaucoup plus gros (en général 107) et même si le recouvrement utilisé est plus important (en général de l'ordre de 1000),
le nombre de calculs supplémentaires dus aux recouvrements est relativement très faible.
En ce qui concerne la taille des recouvrements ce sont les résultats publiés en 1993 par Andrew Odlyzko qui ont guidé son choix :
x Pi(x) G(Pi(x))
10^2 25 5
10^3 168 15
10^4 1229 35
10^5 9592 65
10^6 78498 95
10^7 664579 135
10^8 5761455 175
10^9 50847534 248
10^10 455052511 329
10^11 4118054813 417
10^12 37607912018 481
10^13 346065536839 635
où 'x' est le dernier nombre entier testé (quant au dernier nombre premier il est strictement inférieur à x),
'Pi(x)' est le nombre de nombres premiers dans [1,x] et enfin 'G(Pi(x))' nous donne la taille minimale des recouvrements.
L'architecture matérielle :
Six ordinateurs sont utilisés [05] : d'une part cinq serveurs de calcul ("C") assurant les calculs proprement dits et d'autre part
un PC dit "Superviseur" ("S") qui assure la répartition des différents calculs sur les serveurs. Toutes ces machines
sont sous Linux et sont raccordées à un serveur de fichiers NFS. Voici les configurations donnant dans l'ordre le nombre maximal de
processeurs [06], la capacité mémoire en Go [07] et enfin un indice de performance [08] :
- C1: {40,263,1}
- C2: {12,198,1.3875}
- C3: {12,148,1.48375}
- C4: {16,131,1.52857}
- C5: {36,528,1.6411}
Les programmes :
Un ensemble de programmes destines à tourner sur des ordinateurs sous Linux ont été écrits :
- Un programme de base P1 en C qui sera exécuté en parallèle sur tous les processeurs utiles des serveurs de calcul et
qui reçoit les arguments suivants :
- Le premier nombre entier PNE à tester (non nécessairement premier).
- Le dernier nombre entier DNE à tester (non nécessairement premier).
- Le nombre de blocs NB définissant le découpage de l'intervalle [PNE,DNE]
- Le nombre de nombres premiers NPP définissant le recouvrement inter-blocs.
- Quelques arguments complémentaires destinés à suivre en particulier la progression du calcul.
Ce programme définit la fonction primordiale 'NextPrime(n)' qui renvoie le premier nombre premier qui suive strictement le nombre 'n'
en utilissnt les tests de primalité de Miller-Rabin rendus déterministes. Une boucle principale génère les NB blocs
de l'intervalle [PNE,DNE] en intégrant évidemment le recouvrement, puis une boucle interne balaye successivement chacun de ces NB blocs
afin de calculer les différences définissant le processus. A priori cette boucle est répétée NNP fois,
mais en fait une optimisation fait qu'elle est interrompue dès que n'apparaissent plus que des '0's, des '1's ou des '2's.
A un instant donné, toutes les occurences de P1 sur les différents serveurs Ci seront exécutées avec
la priorité la plus basse [09] ce qui, associé à la très faible "consommation" mémoire [07],
minimise la gène causée aux éventuels autres utilisateurs.
- Un script P2 en Cshell qui est exécuté sur S et qui distribue équitablement les calculs à effectuer à raison
d'un bloc par processeur, puis attend que tous les blocs aient été calculés.
Il s'agit là d'une allocation statique des blocs aux processeurs. Mais étant donné que tous les blocs ne demandent
pas le même temps de calcul [10], il est évident qu'une allocation dynamique aurait été préférable.
Pour ce faire, il aurait suffit de créer des blocs plus petits mais plus nombreux, puis de les placer dans une file d'attente.
Ensuite, dès qu'un processeur quelconque aurait été libre, il aurait prélevé le bloc de tête et ce jusqu'à ce
que la file soit vide. Mais étant donné qu'il y a plusieurs serveurs de calcul différents, cette file d'attente aurait du être
un fichier partagé NFS. Or malheureusement, même lorsqu'un serveur NFS est configuré comme il le faut, l'exclusion des
phases critiques de mise à jour d'un fichier partagé n'est pas fiable à 100% : les expériences faites l'ont montré et ont donc
contraint à implémenter l'allocation statique...
- Un script P3 en Cshell qui est exécuté sur S et qui découpe le calcul complet en sous-calculs soumis à P2
et qui ne demanderont chacun qu'environ cinq heures. Cela permet d'interrompre le calcul complet (volontairement ou en cas de défauts matériels) et de le
reprendre en n'ayant perdu que quelques heures, mais sans voir disparaitre des informations utiles.
P3 permet de plus de répartir dans le temps le lancement des différents P2's : c'est ainsi que, pour le record du 05/10/2025,
les calculs n'ont eu lieu que durant les week-ends et la nuit en semaine.
5-Les résultats :
Les premiers calculs ont commencé le samedi 20/09/2025 à 11:14:28 puis ont été interrompus plusieurs jours à
cause de l'indisponibilité des serveurs de calcul.
Le calcul définitif s'est terminé [11] le dimanche 05/10/2025 à 20:59:18 (heure de Paris, France) comme je l'ai
signalé dans un mail à Jean-Paul Delahaye à 22:36:20 lui indiquant la fin de la dernière étape (qui concernait les nombres premiers de
75.000.000.000.000 à 100.000.000.000.000). Et cela confirmait un mail que je lui avais adressé le 25/09/2025 à 07:17:47 :
Bonne nouvelle : G(Pi(2x1013))=693
qui montrait que G(Pi(1014)) serait supérieure ou égale à 693. Le 05/10/2025 à 20:59:18, je pouvais donc affirmer :
G(Pi(1014))=693
Le record d'Andrew Odlyzko datant de 1993 était battu !
Simon Plouffe [12] annonçait le mardi 07/10/2025 à 02:25 pm (East Time) avoir montré,
lui-aussi, que G(Pi(1014))=693,
plus de 24 heures après moi...
Il est très important de noter que Simon Plouffe et moi-même n'avons utilisé ni les mêmes méthodes, ni les mêmes programmes [13].
Le fait que nous trouvions tous les deux et indépendamment le même résultat garantit l'exactitude de la valeur 693.
Voici quelques informations relatives à la répartition des calculs sur les serveurs lors du calcul du premier record :
Le calcul continue actuellement au-delà de 1x1014 et se situe le 10/11/2025 dans [3x1014,10x1014].
De nouveaux records apparaissent au fur et à mesure :
6-Les records successifs :
G(Pi(x)) = G(Pi(1.000x1014))=693 x ∈ [19563862928347,19595015607259] -05/10/2025, 20:59:18-
G(Pi(x)) = G(Pi(1.100x1014))=701 x ∈ [108623442367669,108652647975061] -24/10/2025, 16:45:28-
G(Pi(x)) = G(Pi(1.145x1014))=744 x ∈ [144875389408103,144906542056021] -27/10/2025, 12:10:26-
G(Pi(x)) = G(Pi(2.200x1014))=773 x ∈ [218200934579443,218228193179959] -03/11/2025, 01:39:05-
G(Pi(x)) = G(Pi(2.800x1014))=788 x ∈ [277889408099683,277908878538719] -08/11/2025, 12:39:52-
Copyright © Jean-François COLONNA, 2025-2025.
Copyright © CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / École polytechnique, Institut Polytechnique de Paris, 2025-2025.
