🔢 mathematics

Minimum Steps to reach to a Smaller Number in 3n+1/Collatz Process

Cet article analyse le temps d'arrêt et la structure de cycle de l'itération de Collatz normalisée pour prouver que le cycle trivial en 1 est l'unique orbite périodique admissible en démontrant qu'aucun cycle fini non trivial n'est compatible avec le processus.

Auteurs originaux : Daohang Sha

Publié 2026-01-28

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Daohang Sha

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La vue d'ensemble : Le jeu du « 3n + 1 »

Imaginez un jeu joué avec des nombres. Vous choisissez un nombre de départ, et vous suivez deux règles simples :

Si le nombre est pair : Divisez-le par deux.
Si le nombre est impair : Triplez-le, ajoutez un, puis divisez-le par deux.

Vous continuez ainsi encore et encore. La célèbre Conjecture de Collatz demande : Peu importe le nombre par lequel vous commencez, finirez-vous toujours par atteindre le nombre 1 ?

La plupart des mathématiciens pensent que la réponse est « oui », mais personne ne l'a encore prouvé. Ce papier de Daohang Sha tente de prouver qu'il n'existe pas de « boucles » (cycles) autres que celle du chiffre 1.

La stratégie de l'auteur : Cartographier le voyage

Sha traite la séquence de mouvements (division par deux ou triplement) comme un code binaire (une chaîne de 0 et de 1).

0 représente une étape de « division par deux ».
1 représente une étape de « triplement ».

Considérez un nombre de départ spécifique comme un voyageur. Le papier analyse la « carte » (la séquence de 0 et de 1) que suit le voyageur. L'auteur se concentre sur un type de voyageur spécifique : ceux dont les nombres de départ laissent un reste de 3 lorsqu'ils sont divisés par 4 (comme 3, 7, 11, 15, etc.).

Concepts clés expliqués

1. Le « Temps d'arrêt » (Quand devient-on plus petit ?)

Imaginez que vous faites une randonnée en montagne. Parfois, vous faites un pas vers le haut (l'étape « 1 », qui rend le nombre plus grand), et parfois, vous faites un pas vers le bas (l'étape « 0 », qui rend le nombre plus petit).

Temps d'arrêt : C'est le moment où vous faites enfin assez de pas vers le bas pour être plus bas que là où vous avez commencé.
La thèse du papier : Sha calcule les scénarios du « meilleur cas » et du « pire cas » pour savoir combien de temps dure cette randonnée. Il montre que pour n'importe quelle longueur de randonnée donnée, il existe une limite mathématique à la façon dont vous pouvez descendre.

2. Le problème du « Cycle » (La boucle infinie)

Un « cycle » serait comme des montagnes russes qui montent et descendent, mais qui finissent par revenir exactement à l'endroit même où vous avez commencé, créant une boucle infinie qui ne descend jamais jusqu'en bas (1).

L'objectif : Le papier tente de prouver qu'une telle boucle est impossible pour n'importe quel voyage fini.

3. L'analogie de l'« Équilibre Parfait »

Pour qu'un cycle existe, le nombre devrait croître et décroître d'une manière si parfaitement équilibrée qu'il reviendrait exactement à son point de départ.

La métaphore mathématique : Imaginez une balance. D'un côté, vous avez des puissances de 2 (division par deux). De l'autre côté, vous avez des puissances de 3 (triplement).
Pour qu'un cycle existe, la balance devrait s'équilibrer parfaitement : $2^s = 3^r$ (où $s$ est le nombre de pas vers le bas et $r$ le nombre de pas vers le haut).
La réalité : Sha souligne qu'une puissance de 2 (comme 2, 4, 8, 16...) ne pourra jamais être égale à une puissance de 3 (comme 3, 9, 27, 81...). Elles sont comme deux langues différentes qui ne pourront jamais traduire exactement la même phrase. Parce qu'elles ne peuvent jamais être égales, la balance ne pourra jamais s'équilibrer parfaitement.

Les principales conclusions

1. Le piège du « Presque arrivé »
À mesure que le voyage devient de plus en plus long (plus d'étapes), le ratio entre le « triplement » et la « division par deux » se rapproche incroyablement d'un équilibre parfait. C'est comme un funambule qui se rapproche de plus en plus de la ligne centrale.

Le papier montre qu'à mesure que la séquence s'allonge, le nombre final se rapproche de plus en plus du nombre de départ ( $F_q(m)/m \to 1$ ).
Cependant, il n'atteint jamais 1. Il s'en approche infiniment, mais il reste toujours un minuscule écart non nul.

2. La barrière du « Fini »
Parce que l'écart entre les puissances de 2 et de 3 ne peut jamais être de zéro, un « cycle parfait » est mathématiquement impossible pour n'importe quel nombre fini d'étapes.

Analogie : Imaginez essayer de construire un pont avec des briques de tailles légèrement différentes. Vous pouvez rapprocher les extrémités, mais si les briques ne sont jamais de la taille exacte, vous ne pourrez jamais fermer l'écart parfaitement sans laisser un vide.
Par conséquent, un « cycle non trivial » (une boucle qui n'inclut pas le nombre 1) ne peut pas exister.

3. Le seul port sûr
Le papier conclut que la seule fois où le processus se répète réellement est la boucle triviale au nombre 1 (1 $\to$ 4 $\to$ 2 $\to$ 1). Tout autre nombre de départ finira par briser le motif et se diriger vers 1, plutôt que de rester coincé dans une autre boucle.

Résumé

Daohang Sha utilise une carte détaillée des étapes de « montée » et de « descente » pour montrer que, bien que les nombres dans le jeu de Collatz puissent se rapprocher très près de la formation d'une boucle parfaite, la mathématique fondamentale des puissances de 2 et de 3 rend impossible la fermeture complète du cercle.

Ce qu'il faut retenir : Si vous commencez avec n'importe quel nombre, vous pourriez rester coincé dans une danse très longue et compliquée, mais vous ne trouverez jamais une piste de danse qui revient au point de départ sans finir par sortir de la piste pour atterrir sur le 1. L'« boucle infinie » est une impossibilité mathématique.

Résumé Technique : Sur les bornes du temps d'arrêt et des nombres de cycles dans le processus de Collatz

Énoncé du Problème
Cet article traite du problème $3n + 1$ (conjecture de Collatz), en se concentrant spécifiquement sur l'itération de Collatz normalisée définie par $F_0(n) = n/2$ pour $n$ pair et $F_1(n) = (3n+1)/2$ pour $n$ impair. L'objectif principal est d'analyser le temps d'arrêt et la structure des cycles de ce processus. L'auteur restreint l'analyse aux valeurs de départ impaires $m \equiv 3 \pmod 4$ avec un temps d'arrêt $s \ge 4$ , car les cas plus petits sont trivialement vérifiables. La question centrale est de savoir si des cycles finis non triviaux (orbites périodiques autres que le cycle trivial à 1) peuvent exister au sein de cette itération.

Méthodologie
L'article emploie une description récursive de séquences binaires admissibles pour modéliser le processus de Collatz. Une séquence $q$ de longueur $s$ contenant $r$ uns (représentant les étapes impaires) et $s-r$ zéros (représentant les étapes paires) est utilisée pour définir la transformation $F_q(n)$ .

Les composantes méthodologiques clés incluent :

Représentation par séquence binaire : La transformation est exprimée par $F_q(n) = \frac{3^r n + \sum_{i=1}^r 3^{r-i} 2^{l(i)-1}}{2^s}$ , où $l(i)$ désigne la position du $i$ -ème '1' dans la séquence.
Construction d'arbre récursif : L'auteur introduit un arbre de séquences enraciné modifié (Figure 1) pour générer des séquences admissibles. Cet arbre est construit en insérant des sous-chaînes spécifiques ("1" ou "10") avant le bloc terminal de zéros, garantissant une correspondance unique entre les séquences et les entiers de départ.
Analyse de théorie des nombres : L'article utilise les propriétés de l'arithmétique modulaire (spécifiquement modulo $2^s$ et modulo 4) et l'unicité des expansions binaires pour établir une bijection entre les séquences binaires admissibles $q$ et les entiers $m \equiv 3 \pmod 4$ .
Dérivation d'inégalités : En appliquant l'inégalité de réarrangement, l'auteur dérive des bornes inférieures et supérieures pour le terme de sommation $\sum_{i=1}^r 3^{r-i} 2^{l(i)-1}$ , qui représente la composante additive de l'itération.

Contributions Clés et Résultats

Unicité de la représentation (Théorème 2.10) : L'article établit une bijection entre les séquences binaires admissibles $q$ et les entiers $m \equiv 3 \pmod 4$ . Chaque entier de ce type provient de manière unique d'une séquence spécifique dans l'arbre construit, et chaque séquence correspond à un entier unique satisfaisant $F_q(m) < m$ .
Bornes sur le terme additif (Théorèmes 2.3 & 2.4) : Le terme de sommation dans la formule de l'itération est borné. La valeur minimale est $3^r - 2^r$ (survenant lorsque tous les '1' sont au début de la séquence), et la valeur maximale est atteinte lorsque les '1' sont distribués selon l'espacement logarithmique de l'arbre de séquence.
Non-existence de cycles finis non triviaux (Théorèmes 2.11 & 3.1) :
- L'article prouve que pour toute séquence finie, $F_q(4i-1) \neq 4i-1$ . Un cycle nécessiterait l'égalité $2^s = 3^r$ , ce qui est impossible pour des entiers $s, r > 0$ .
- Par conséquent, aucun cycle fini non trivial ne peut se produire. La seule orbite périodique admissible est le cycle trivial à 1.
Comportement asymptotique du ratio (Théorème 3.2) : L'article dérive des bornes pour le ratio $F_q(m)/m$ $F_{q} (m) / m$ . Il montre que lorsque la longueur de la séquence augmente (et que $r \to \infty$ $r \to \infty$ ), le ratio $3^r/2^s$ $3^{r} / 2^{s}$ tend vers 1, mais ne l'atteint jamais.
- Le ratio $F_q(m)/m$ est borné par $1 - \epsilon_1 < F_q(m)/m < 1 + \epsilon_2$ .
- Lorsque $r \to \infty$ , $\lim F_q(m)/m \to 1$ .
Bornes du nombre de cycles : L'article fournit des bornes inférieures et supérieures pour un hypothétique nombre de cycle non trivial $m_c$ . La borne inférieure est donnée par $m_c \ge \frac{3^r - 2^r}{2^s - 3^r}$ . Pour de grandes valeurs de $r$ (par exemple, $r \approx 4.3 \times 10^{14}$ ), la borne inférieure est approximativement de $7.5 \times 10^{14}$ , tandis que la borne supérieure est d'environ $5.12 \times 10^{29}$ .

Signification et Revendications
L'article affirme démontrer que les exigences structurelles pour un cycle fini non trivial dans l'itération de Collatz normalisée sont inatteignables. Spécifiquement, l'existence d'un tel cycle nécessiterait une identité exacte entre les puissances de 2 et de 3 ( $2^s = 3^r$ ), ce qui est mathématiquement impossible.

L'auteur conclut que :

Le temps d'arrêt dans le processus de Collatz ne possède pas de borne supérieure finie.
Le ratio $F_q(m)/m$ tend vers l'unité à mesure que la longueur de la séquence augmente, mais ne l'atteint jamais pour toute séquence finie.
Cette obstruction structurelle, combinée aux bornes dérivées, exclut la possibilité de cycles finis non triviaux.
Par conséquent, le cycle trivial à 1 est la seule orbite périodique admissible.

L'article s'appuie sur la vérification computationnelle pour les petits cas et sur des bornes théoriques pour les grands $r$ , notant que bien que l'écart entre $3^r$ et $2^s$ devienne infinitésimal pour de grands paramètres (par exemple, $1 - 3^r/2^s \approx 10^{-15}$ ), il reste strictement non nul, empêchant la formation d'un cycle.