Fonction de Collatz
La fonction de Collatz, inventée par Lothar Collatz en 1937, est une fonction applicable à tout entier positif n, définie :
- soit par : n/2 si n est pair, 3 n + 1 s'il est impair ;
- soit comme la fonction précédente appliquée récursivement tant que le résultat n'est pas égal à 1.
Dans sa 2e version la fonction ne peut donner comme résultat que 1, mais elle pourrait tourner indéfiniment sans renvoyer de résultat (on n'en connaît cependant aucun exemple, voir ci-dessous).
Suite de Collatz
[modifier | modifier le code]On appelle suite de Collatz une suite de nombres générée par la fonction de Collatz (1re version) appliquée récursivement à partir d'un nombre initial n (« graine »).
Exemples
[modifier | modifier le code]- Si n = 1, la suite est périodique : 1, 4, 2, 1, 4, 2, 1,...
- Si n = 3, la suite devient périodique (une fois qu'on a atteint 1) : 3, 10, 5, 16, 8, 4, 2, 1,...
- Si n = 27, la suite comporte 111 entiers successifs sans régularité apparente, dont le plus grand est 9 232 et le dernier 1, ensuite elle est périodique comme les précédentes[1].
Conjecture de Collatz
[modifier | modifier le code]La conjecture de Collatz, ou conjecture de Syracuse, énonce qu'une suite de Collatz passe toujours par 1[a]. Elle a été vérifiée pour toutes les graines inférieures à environ 1020 et démontrée pour « presque tous »[b] les entiers[2], mais en 2024 on ne sait toujours pas si elle est vraie, fausse ou indécidable[1].
Notes et références
[modifier | modifier le code]Notes
[modifier | modifier le code]- Autrement dit, la conjecture est que la fonction de Collatz (2e version) donne toujours le résultat 1 au bout d'un nombre fini d'opérations.
- Le nombre M des entiers inférieurs à N qui vérifient la conjecture est équivalent à N quand N → ∞, c'est-à-dire que M/N → 1.
Références
[modifier | modifier le code]- L. G., « Une percée dans la conjecture de Collatz », Pour la science, no 509, , p. 8.
- (en) Terence Tao, « Almost all orbits of the Collatz map attain almost bounded values », sur Arxiv.org (consulté le ).
