AccueilđŸ‡«đŸ‡·Chercher

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

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

  • 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

La conjecture de Collatz, ou conjecture de Syracuse, Ă©nonce qu'une suite de Collatz passe toujours par 1[alpha 1]. Elle a Ă©tĂ© vĂ©rifiĂ©e pour toutes les graines infĂ©rieures Ă  environ 1020 et dĂ©montrĂ©e pour « presque tous Â»[alpha 2] les entiers[2], mais en 2020 on ne sait toujours pas si elle est vraie, fausse ou indĂ©cidable[1].

Notes et références

Notes

  1. 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.
  2. 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

  1. L. G., « Une percĂ©e dans la conjecture de Collatz », Pour la science, no 509,‎ , p. 8.
  2. (en) Terence Tao, « Almost all orbits of the Collatz map attain almost bounded values », sur Arxiv.org (consulté le ).

Voir aussi

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.