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 2^e 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

On appelle suite de Collatz une suite de nombres générée par la fonction de Collatz (1^re version) appliquée récursivement à partir d'un nombre initial $n$ (« graine »).

Exemples

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

Article détaillé : Conjecture de Syracuse.

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 10²⁰ 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

Notes

↑ Autrement dit, la conjecture est que la fonction de Collatz (2^e 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 \to \infty$ , c'est-à-dire que $M / N \to 1$ .

Références

↑ ^{a et b} L. G., « Une percée dans la conjecture de Collatz », Pour la science, n^o 509,‎ mars 2020, p. 8.
↑ (en) Terence Tao, « Almost all orbits of the Collatz map attain almost bounded values », sur Arxiv.org (consulté le 26 février 2020).

Voir aussi

Arithmétique et théorie des nombres

[2] Autrement dit, la conjecture est que la fonction de Collatz (2^e version) donne toujours le résultat $1$ au bout d'un nombre fini d'opérations.

[3] Le nombre $M$ des entiers inférieurs à $N$ qui vérifient la conjecture est équivalent à $N$ quand $N \to \infty$ , c'est-à-dire que $M / N \to 1$ .

[LG2020-1] {a et b} L. G., « Une percée dans la conjecture de Collatz », Pour la science, n^o 509,‎ mars 2020, p. 8.

[4] (en) Terence Tao, « Almost all orbits of the Collatz map attain almost bounded values », sur Arxiv.org (consulté le 26 février 2020).

[1]

[a]

[b]

[2]