nombre chanceux d'Ulam

Imaginez une file de nombres naturels écrits à partir de 1. On retire d'abord un nombre sur deux : les nombres placés aux rangs pairs disparaissent. Dans la file raccourcie, le nombre 3 occupe le deuxième rang ; il impose alors une nouvelle élimination, aux rangs multiples de 3. Les survivants forment une suite qui se transforme encore et encore.

Un nombre chanceux est un nombre qui reste dans cette file après toutes les étapes. Le mot « chanceux » décrit cette survie par éliminations successives, et non une propriété de hasard.

Un nombre chanceux d'Ulam est un entier naturel qui survit à un crible itératif. La liste initiale est 1, 2, 3, 4, 5, … ; le rang d'un élément est sa position dans la liste courante, en commençant par 1. La première étape retire les éléments de rang pair et conserve donc 1, 3, 5, 7, 9, … .

Après cette étape, le deuxième élément est 3. La deuxième règle retire les éléments dont le rang, dans la liste alors obtenue, est un multiple de 3. Le troisième élément encore présent est 7 ; l'étape suivante retire donc les éléments de rang multiple de 7. À chaque tour, 1 reste le point de départ et n'est pas repris comme multiplicateur ; le premier survivant non encore utilisé comme règle fournit alors le rang multiplicateur suivant.

Les entiers qui ne sont retirés à aucune étape appartiennent à la suite des nombres chanceux. Cette définition dépend de la liste ordonnée et de ses rangs : elle ne signifie pas que l'entier lui-même est divisible par 3 ou par 7. Un nombre à la fois premier et chanceux est appelé nombre premier chanceux.

Pour suivre le crible sur les premiers rangs, on part de la suite des entiers naturels à partir de 1. Les données utiles sont la première liste, la règle de retrait aux rangs pairs, puis les deux premiers rangs multiplicateurs suivants : 3 et 7.

La liste initiale commence ainsi : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, … .

1. Le rang 1 contient 1 et les rangs pairs contiennent 2, 4, 6, 8, 10, 12, 14, … ; on les retire. Il reste 1, 3, 5, 7, 9, 11, 13, 15, … .
2. Le deuxième survivant est 3. Dans cette nouvelle liste, les rangs 3, 6, 9, … contiennent 5, 11, 17, … ; on les retire. Il reste 1, 3, 7, 9, 13, 15, 19, 21, … .
3. Le troisième survivant est 7. On retire alors les éléments placés aux rangs 7, 14, 21, … de la liste courante.

Après les deux premières éliminations, 1, 3, 7, 9, 13 et 15 sont donc survivants dans l'extrait affiché. Le contrôle consiste à recompter les positions dans la liste après chaque étape : la position de 5, par exemple, est 3 après la première étape, ce qui explique son retrait à la deuxième.

Pour produire les premiers nombres chanceux, on écrit une liste assez longue, on numérote ses positions à partir de 1, puis on supprime les positions paires. On traite 1 comme point de départ déjà utilisé et on recommence avec le premier survivant non encore utilisé comme règle : 3, puis 7.

Pour vérifier un résultat à la main, on entoure les survivants et on recompte les rangs après chaque suppression. Cette vérification est préférable à la recherche de multiples de 3 ou de 7 parmi les valeurs elles-mêmes, car le crible agit sur les positions.

Pour une longue liste, un programme peut conserver un tableau ordonné et marquer les rangs multiples de la règle courante. Le critère de choix est alors la taille de la liste : la méthode manuelle convient à un petit extrait, tandis que le tableau automatisé évite les recomptages nombreux.

Le nombre chanceux d'Ulam ne doit pas être confondu avec un nombre premier. Un nombre premier est un entier naturel supérieur à 1 qui possède exactement deux diviseurs positifs ; le test porte sur ses diviseurs. Pour un nombre chanceux, le test porte sur sa survie dans le crible des rangs. Ainsi, 9 apparaît dans l'extrait des survivants après les deux premières étapes, bien que 9 ne soit pas premier.

Le crible des nombres chanceux ne se confond pas non plus avec le crible d'Ératosthène. Le premier élimine selon des rangs dans une liste qui se resserre ; le second élimine les multiples de nombres premiers dans les valeurs. Leur ressemblance vient du caractère itératif, pas d'une règle d'élimination identique.

Le piège principal est de confondre rang et valeur. Après la première étape, la valeur 5 occupe le troisième rang ; elle est donc supprimée à l'étape commandée par 3, même si 5 n'est pas un multiple de 3. À la place, il faut renuméroter la liste courante avant chaque nouvelle suppression.

La règle est sans fin dans sa formulation : chaque nouveau multiplicateur vient du premier survivant non encore utilisé comme multiplicateur, après que 1 a été traité comme point de départ. Un calcul sur une liste finie ne prouve donc que la survie dans la portion examinée ; il ne suffit pas, à lui seul, à établir qu'un entier survivra à toutes les étapes.

Le nombre 1 est conservé dès la première étape et reste le premier élément de la liste. Il ne doit pas être appelé premier chanceux : 1 n'est pas un nombre premier, alors que l'expression « nombre premier chanceux » exige les deux propriétés.

Le crible d'Ératosthène offre un prolongement naturel pour comparer deux façons d'éliminer des entiers : le crible d'Ulam travaille sur les rangs successifs, tandis que le crible d'Ératosthène travaille sur les multiples dans les valeurs. Cette comparaison aide à mesurer exactement l'analogie annoncée par la définition.

Pour approfondir l'arrière-plan de la terminologie, la fiche « Ulam Stanislaw » présente la personne associée à l'introduction du crible et de son nom.