Suite d'Euclide-Mullin

La Suite d'Euclide-Mullin est une suite infinie de nombres premiers distincts, dans laquelle chaque terme est le plus petit diviseur premier du produit des termes précédents plus un, en partant du nombre 2. Son appellation fait référence au mathématicien grec Euclide, car sa définition repose sur la même idée que celle de la preuve d'Euclide de l'infinitude des nombres premiers, et à Albert Mullin, qui a posé des questions sur cette suite en 1963.

Les 51 premiers éléments de la suite sont (Modèle:OEIS) :

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957, 887, 71, 7127, 109, 23, 97, 159227, 643679794963466223081509857, 103, 1079990819, 9539, 3143065813, 29, 3847, 89, 19, 577, 223, 139703, 457, 9649, 61, 4357, 87991098722552272708281251793312351581099392851768893748012603709343, 107, 127, 3313, 227432689108589532754984915075774848386671439568260420754414940780761245893, 59, 31, 211,...

Ce sont les seuls termes connus à la date de Modèle:Date-. Pour trouver le terme suivant 211, il faut trouver le plus petit diviseur premier d'un nombre de 335 chiffres (que l'on sait être composé).

Définition

Posant $a_1=2$, le n-ième élément de la suite $a_n$est le plus petit diviseur > 1 (qui est forcément premier) de $\left(\prod _{i<n}{a}_i\right)+1$.

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

De même, $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.

Propriétés

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 $a_i$ne peut diviser $\left(\prod _{i<n}{a}_i\right)+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.

Conjecture

Albert Mullin s'est demandé en 1963 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 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 Modèle:OEIS.

Suites apparentées

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 (Modèle: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,..., Modèle: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 (Modèle: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é de garder la relation de récurrence : $a_n$= plus petit diviseur > 1 de $\left(\prod _{i<n}{a}_i\right)+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 a été de considérer toutes les sommes $\prod _{i\in I}{a}_i+\prod _{j\in J}{a}_j$ où $\{I,J\}$ est une partition de $\{1,..,n-1\}$ et de poser $a_n$= le plus petit diviseur > 1 de toutes ces sommes, en partant de $a_1=2$. Par exemple, $a_2=3$, $a_3=5$ et $a_4$ est le plus petit diviseur > 1 de 30+1, 6+5, 2+15, et 10+3, d'où $a_4=11$. Là encore on obtient une suite de nombres premiers distincts car aucun $a_i$ pour $i$ dans $\{1,..,n-1\}$ ne peut diviser $\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,..., (Modèle: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).

Voir aussi

Articles connexes

• Nombre d'Euclide
• Suite de l'électrocardigramme, qui constitue une permutation des entiers naturels non nuls

Liens externes

• Modèle:MathWorld