Le cheval de trois, un algo de recherche de nombres premiers jumeaux ?

Conjecture.
jeudi 1er octobre 2020
par  Alain BUSSER , Franck JEAN-ALBERT , Nathalie CARRIÉ

Gabriel COURVOISIER, professeur de mathématiques à la retraite, a un passe temps qui consiste à jongler avec les nombres. Lors de ses activités, il a conçu un algorithme de recherche de couples de nombres premiers jumeaux. N’étant guère porté sur la programmation et l’informatique au sens large, Gabriel a fait tourner son algorithme manuellement à grands renforts de papier, de feutre, d’huile de coude et de matière grise. Il nous a présenté son algorithme lors d’un séminaire IREMI et nous nous sommes empressés de le coder pour voir si on pouvait aller plus loin qu’à la main.

Les nombres premiers fascinent les mathématiciens depuis l’antiquité. L’étude des propriétés des nombres entiers, qui semblait être une branche des mathématiques dénuée d’utilité concrète ou d’applications techniques, s’est révélée fortement utile dans les années 1970 avec la conception des systèmes de cryptographie basés sur des propriétés arithmétiques abstraites. Le système de cryptographie à clef publique RSA toujours largement utilisé en est l’exemple canonique. La frontière entre les mathématiques appliquées et « non encore appliquées » semble être de plus en plus floue.

Dans les éléments d’Euclide, qui remontent à la Grèce antique, il est démontré qu’il existe une infinité de nombres premiers.

Les nombres premiers jumeaux sont des couples de nombres premiers qui ne différent que de 2. Par exemple, les nombres 3 et 5 forment un couple de nombres premiers jumeaux, tout comme 87179 et 87181. La question de savoir s’il existe une infinité de tels couples de nombres premiers jumeaux est encore ouverte. Pour plus d’informations sur le sujet voir par exemple Gourdon & Sebah

Les méthodes utilisées pour chercher des couples de premiers jumeaux sont des méthodes de cribles, inspirées de l’antique crible d’Ératosthenes étudié dans l’enseignement secondaire en France. Gabriel a développé son algorithme en ayant en tête l’idée de créer un crible. Il procède en créant un tableau infini constitué de suites arithmétiques :

Les termes initiaux des suites sont définis par :

  • $A_k=k(3 k - 1)$
  • $B_k=3k^2$
  • $C_k=3k^2$
  • $D_k=k(3 k + 1)$

l’entier naturel non nul $k$ étant quelconque, on a une infinité dénombrable de termes initiaux.

Les raisons associées à chacun de ces termes initiaux sont respectivement $6k-1$, $6k-1$, $6k+1$ et $6k+1$ .

Ainsi, le tableau infini est constitué des suites arithmétiques :

  • $A_{k,n}=k(3 k - 1)+n(6k-1)$
  • $B_{k,n}=3k^2+n(6k-1)$
  • $C_{k,n}=3k^2+n(6k+1)$
  • $D_{k,n}=k(3 k + 1)+n(6k+1)$
    les nombres $k$ et $n$ étant des entiers naturels, avec $k$ non nul.

Étant donné ce tamis infini, Gabriel conjecture que si un nombre entier $c$ passe à travers ce tamis infini, alors les deux nombres $12c-1$ et $12c+1$ sont des nombres premiers jumeaux. Gabriel a constaté que ce crible ne sort pas tous les nombres premiers jumeaux. Un nombre $c$ manquant dans le tableau est qualifié graine et les deux jumeaux ayant la même graine sont appelés monozygotes par Gabriel [1].

Voici en image la conjecture de Gabriel :

Les questions qu’il est légitime de se poser sont les suivantes :

  • La conjecture est-elle valide ?
  • Le nombre de graines qui passent à travers le tamis est-il infini ?

Voici les documents qui ont permis à faire Gabriel Courvoisier de faire tourner son algorithme à la main, afin d’obtenir des couples de premiers jumeaux jusqu’à 10 000 :

  • La conjecture :
    Définition des suites et conjecture de Gabriel Courvoisier
    Scan de manuscrit.
  • La bande contenant les termes initiaux :
Premiers termes & raisons, version manuscrite.
Scan d’un manuscrit.
  • Les termes manquants trouvés :
Début du registre des nombres trouvés et manquants
Document manuscrit
Fin du registre des nombres trouvés et manquants
Document Manuscrit scanné
Listes des manquants, les graines.
Document manuscrit scanné

Il procède ainsi. Commençant pas le nombre 1, premier candidat à être une graine, il observe si celui-ci serait présent dans la bande contenant les termes initiaux. Le nombre 1 est vraisemblablement manquant, il passe au candidat suivant, le nombre 2. On notera au passage que les deux nombres obtenus avec 1 comme « graine » sont effectivement des premiers jumeaux, à savoir 11 et 13.
Le nombre 2 est présent ; puisque $A(1 ;0)=2$.
Le nombre 3 est également présent, on le trouve en $B(1 ;0)=C(1 ;0)=3$.
Passant au nombre suivant, il incrémente lorsque nécessaire les termes des suites arithmétiques afin de chercher le nombre candidat plus haut dans les suites arithmétiques.
Pour conserver en mémoire les termes courants de chacune des suites, il a utilisé des étiquettes cartonnées sur lesquelles il modifiait les valeurs courantes au fur et à mesure.
Chaque fois qu’un nombre est rencontré quelque part, il l’ajoute dans son registre des nombres trouvés et manquants, qu’il dresse ainsi au fur et à mesure.
Après avoir fait tourner son algorithme manuellement, il a pu vérifier la validité de sa conjecture pour tous les nombres qualifiés de manquants jusqu’à 10 000.
Cet imposant travail de calcul manuel nous a été présenté lors du séminaire IREMI du 4 mars 2020 sur le campus du Tampon de l’université de la Réunion. Dominique Tournès a judicieusement suggéré d’implémenter l’algorithme afin de tester la conjecture sur une plage plus grande. En voici une implémentation en Python et en Snap! :

L’algorithme en python

  1. from math import sqrt,ceil
  2.  
  3. # test basique
  4. def est_premier(p):
  5.         if p%2==0 or p%3==0:
  6.                 return False
  7.         else:
  8.                 n=1
  9.                 while  3*n+2<sqrt(p):
  10.                         if (p%(3*n+2)==0):
  11.                                 return False
  12.                         n=n+1
  13.         return True
  14.  
  15. def a(k):
  16.         return k*(3*k-1)
  17. def b(k):
  18.         return 3*k**2
  19. def c(k):
  20.         return 3*k**2
  21. def d(k):
  22.         return k*(3*k+1)
  23.  
  24. # limite de la recherche:
  25. #n=int(input("taille max de la graine? "))
  26. n=1000000
  27.  
  28. # definition de la borne de droite
  29. def bd(n):
  30.         epsilon=10 # bricolage
  31.         return 4*(ceil((sqrt(12*n+1)-1)/6)+epsilon)
  32.  
  33. # initialisation:
  34. k=1
  35. borne_droite=bd(n)
  36. liste,raisons=[],[]
  37. while k<=borne_droite:
  38.         liste=liste+[a(k),b(k),c(k),d(k)]
  39.         raisons=raisons+[6*k-1,6*k-1,6*k+1,6*k+1]
  40.         k+=1
  41.  
  42. # on part du candidat 1, (la première graine potentielle)
  43. c=1
  44. borne=-1
  45. while c<n:
  46.         trouve=False
  47.         pos=0
  48.         # on redescend d'un cran partout au cas où ;-)
  49.         for k in range(borne+1):
  50.                 liste[k]-=raisons[k]
  51.         # on démarre  
  52.         while liste[pos]<c:
  53.                 while liste[pos]<c:
  54.                         liste[pos]+=raisons[pos] # on monte
  55.                 if liste[pos]==c:
  56.                         trouve=True
  57.                 pos+=1 # on avance
  58.         if liste[pos]==c:
  59.                 trouve=True
  60.         if not trouve:
  61.                 print("graine: ",c,"jumeaux: ",12*c-1,12*c+1,"test: ",est_premier(12*c-1) and est_premier(12*c+1))
  62.        
  63.         # candidat suivant, la variable borne permet
  64.         # de redescendre un chouïa histoire d'avoir rien raté quand on ajoute une raison...
  65.         c+=1
  66.         borne=pos
  67.  

Télécharger

Implémentation de l’algorithme avec Snap!

Voici le script Snap! :

Script Snap! des nombres premiers monozygotes


[1Mais pourquoi les appelle-t-il monozygotes ? Voir cet article de Wikipédia : Jumeaux monozygotes


Portfolio

PNG - 151.4 ko PNG - 416.1 ko

Commentaires

Navigation

Articles de la rubrique