Suite d'Euclide-Mullin

Posant ${\displaystyle a_{1}=2}$, le n-ième élément de la suite ${\displaystyle a_{n}}$est le plus petit diviseur > 1 (qui est forcément premier) de ${\displaystyle {\Bigl (}\prod _{i<n}a_{i}{\Bigr )}+1}$.

Par exemple, ${\displaystyle a_{5}}$ est le plus petit diviseur > 1 de (2 × 3 × 7 × 43) + 1 = 1806 + 1 = 1807 = 13 × 139 ; donc ${\displaystyle a_{5}=13}$.

De même, ${\displaystyle a_{7}}$ est le plus petit diviseur > 1 de (2 × 3 × 7 × 43 × 13 × 53) + 1 = 1 244 335, soit le nombre 5. Ces exemples illustrent pourquoi la suite peut passer d'un nombre très grand à un très petit.

La suite est infinie et ne contient pas de répétitions ; la première affirmation vient de ce que tout entier > 1 possède un plus petit diviseur > 1, et la deuxième vient de ce qu'aucun ${\displaystyle a_{i}}$ne peut diviser ${\displaystyle {\Bigl (}\prod _{i<n}a_{i}{\Bigr )}+1}$.

Ceci prouve donc l'infinitude des nombres premiers, sans passer par un raisonnement par l'absurde comme dans la présentation classique de la preuve d'Euclide.

Albert Mullin s'est demandé en 1963[1] si tous les nombres premiers figuraient dans cette suite et, dans le cas contraire, si le problème du test d'appartenance à la suite pour un nombre donné est calculable. Daniel Shanks[2] a conjecturé, sur la base de l'hypothèse heuristique que la distribution des nombres premiers est aléatoire, que chaque nombre premier apparaît dans la suite. Cependant, bien que l'on sache que des suites présentant des récurrences similaires ne contiennent pas tous les nombres premiers, ce problème reste ouvert pour la suite d'Euclide-Mullin. Le plus petit nombre premier non connu pour être un terme de la suite est 41.

Les positions des nombres premiers de 2 à 97 sont : (? indique que la position était inconnue en 2012)

2 : 1, 3 : 2, 5 : 7, 7 : 3, 11 : 12, 13 : 5, 17 :13, 19 : 36, 23 : 25, 29 : 33, 31 : 50, 37 : 18, 41 : ?, 43 : 4, 47 : ?, 53 : 6, 59 : 49, 61 : 42, 67 : ?, 71 : 22, 73 : ?, 79 : ?, 83 : ?, 89 : 35, 97 : 26 ; cf. la suite A056756 de l'OEIS.

La suite obtenue en prenant le plus grand facteur premier au lieu du plus petit est parfois appelée deuxième suite d'Euclide-Mullin. Elle croit plus rapidement, mais est également non monotone. Les premiers termes sont (suite A000946 de l'OEIS) :

2, 3, 7, 43, 139, 50207, 340999, 2365347734339, 4680225641471129, 1368845206580129, 889340324577880670089824574922371,…

Contrairement à la première suite d'Euclide-Mullin, on sait que cette suite ne recouvre pas tous les nombres premiers, et même que la suite des nombres premiers manquants est infinie : 5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, ..., suite A216227 de l'OEIS,

La suite obtenue en partant de 3 et en retranchant 1 au lieu de l'ajouter est très similaire à la suite d'Euclide-Mullin. Ses premiers termes sont (suite A005265 de l'OEIS) :

3, 2, 5, 29, 11, 7, 13, 37, 32222189, 131, 136013303998782209, 31, 197, 19, 157, 17, 8609, 1831129, 35977, 508326079288931,...

Il a aussi été proposé[3] de garder la relation de récurrence : ${\displaystyle a_{n}}$= plus petit diviseur > 1 de ${\displaystyle {\Bigl (}\prod _{i<n}a_{i}{\Bigr )}+1}$, mais de faire débuter la suite par une famille finie donnée de nombres premiers, la semence de la suite. Par exemple, la suite obtenue en partant de (2, 3) est la suite d'Euclide-Mullin classique, mais pas celle commençant par (2, 3, 5). Cette voie n'a pas permis d'obtenir de suite recouvrant assurément tous les premiers.

Une autre voie[3] a été de considérer toutes les sommes ${\displaystyle \prod _{i\in I}a_{i}+\prod _{j\in J}a_{j}}$ où ${\displaystyle \left\{I,J\right\}}$ est une partition de ${\displaystyle \left\{1,..,n-1\right\}}$ et de poser ${\displaystyle a_{n}}$= le plus petit diviseur > 1 de toutes ces sommes, en partant de ${\displaystyle a_{1}=2}$. Par exemple, ${\displaystyle a_{2}=3}$, ${\displaystyle a_{3}=5}$ et ${\displaystyle a_{4}}$ est le plus petit diviseur > 1 de 30+1, 6+5, 2+15, et 10+3, d'où ${\displaystyle a_{4}=11}$. Là encore on obtient une suite de nombres premiers distincts car aucun ${\displaystyle a_{i}}$ pour ${\displaystyle i}$ dans ${\displaystyle \left\{1,..,n-1\right\}}$ ne peut diviser ${\displaystyle \prod _{i\in I}a_{i}+\prod _{j\in J}a_{j}}$. On obtient la suite 2, 3, 5, 11, 37, 13, 7, 29, 17, 19, 43, 23, 47, 41,..., (suite A167604 de l'OEIS) mais il n'a pas été prouvé que cette suite recouvre tous les premiers.

On peut enfin construire la suite dont chaque terme est le produit des termes précédents +1 (qui est la suite de Sylvester), et considérer la suite des plus petits facteurs premiers des termes de cette suite. Comme la suite d'Euclide-Mullin, il s'agit d'une suite infinie et non-monotone de nombres premiers (donc constitue une autre démonstration de l'infinitude des nombres premiers), mais il est connu qu'elle n'inclut pas tous les nombres premiers (ses termes sont tous, excepté 3, de la forme 6k+1).

• Nombre d'Euclide

• Weisstein, Eric W. "Euclid–Mullin Sequence", MathWorld.