|
Collatz
Lothar (1910-1990)
° Algorithme de
Collatz.
– Algorithme imaginé par
l'allemand Collatz au début des années 1930. On choisit arbitrairement un
nombre entier. S'il est pair, on le divise par 2. S'il est impair, on le
multiplie par 3 et on additionne l'unité. On répète ces opérations à partir
du dernier nombre obtenu jusqu'à ce que la séquence conduise à l'unité où
une boucle se produit. Le nombre 9 exige 19 opérations : 9, 28, 14, 7,
22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Par ailleurs, 55
exige une séquence de 112 opérations jusqu'à l'unité. La séquence atteint
un sommet à 9232.
Il existe des entiers consécutifs qui exigent le même
nombre d'opérations. Les plus petits sont respectivement : (12, 13) pour
9 opérations, (28, 29, 30) pour 18 opérations, (314, 315, 316, 317) pour 37
opérations, (98, 99, 100, 101, 102) pour 25 opérations, (386, 387, 388, 389,
390, 391) pour 120 opérations, (943, 944, 945, 946, 947, 948, 949) pour 36
opérations.
L'algorithme de Collatz a permis de formuler la conjecture dite de
Syracuse : quel que soit l'entier de départ choisi, la suite formée en
appliquant cet algorithme aboutit toujours à 1. En effet, on pense que tout
entier conduit à l'unité puisqu'aucun contre-exemple n'a été trouvé ; mais
on n'a pas pu encore le démontrer.
L'algorithme de Collatz est associé aux
récréations numériques.
© Charles-É. Jean
Index
: C
|
Dépendant des moments et des lieux de sa diffusion,
l'algorithme de Collatz a
successivement été connu comme l’algorithme de Hasse, le problème de
Syracuse, le problème d'Ulam et le problème de Kakutani.
Il est aussi appelé problème des trois n plus un.
|
