🔢 mathematics

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

This paper analyzes the stopping-time and cycle structure of the normalized Collatz iteration to prove that the trivial cycle at 1 is the only admissible periodic orbit by demonstrating that no finite nontrivial cycle is compatible with the process.

Original authors: Daohang Sha

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daohang Sha

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "3n + 1" Game

Imagine a game played with numbers. You pick a starting number, and you follow two simple rules:

If the number is even: Cut it in half.
If the number is odd: Triple it, add one, and then cut it in half.

You keep doing this over and over. The famous Collatz Conjecture asks: No matter what number you start with, will you always eventually reach the number 1?

Most mathematicians believe the answer is "yes," but nobody has proven it yet. This paper by Daohang Sha tries to prove that there are no "loops" (cycles) other than the one at 1.

The Author's Strategy: Mapping the Journey

Sha treats the sequence of moves (halving vs. tripling) like a binary code (a string of 0s and 1s).

0 represents a "halving" step.
1 represents a "tripling" step.

Think of a specific starting number as a traveler. The paper analyzes the "map" (the sequence of 0s and 1s) the traveler follows. The author focuses on a specific type of traveler: those starting with numbers that leave a remainder of 3 when divided by 4 (like 3, 7, 11, 15, etc.).

Key Concepts Explained

1. The "Stopping Time" (When do we get smaller?)

Imagine you are hiking up a mountain. Sometimes you take a step up (the "1" step, which makes the number bigger), and sometimes you take a step down (the "0" step, which makes it smaller).

Stopping Time: This is the moment you finally take enough steps down that you are lower than where you started.
The Paper's Claim: Sha calculates the "best case" and "worst case" scenarios for how long this hike takes. He shows that for any specific length of the hike, there is a mathematical limit to how low you can go.

2. The "Cycle" Problem (The Infinite Loop)

A "cycle" would be like a rollercoaster that goes up and down but eventually returns to the exact same spot you started, creating an infinite loop that never reaches the bottom (1).

The Goal: The paper tries to prove that such a loop is impossible for any finite journey.

3. The "Perfect Balance" Analogy

To have a cycle, the number would have to grow and shrink in such a perfect way that it ends up exactly where it started.

The Math Metaphor: Imagine a scale. On one side, you have powers of 2 (halving). On the other side, you have powers of 3 (tripling).
For a cycle to exist, the scale would have to balance perfectly: $2^s = 3^r$ (where $s$ is the number of steps down and $r$ is the number of steps up).
The Reality: Sha points out that a power of 2 (like 2, 4, 8, 16...) can never equal a power of 3 (like 3, 9, 27, 81...). They are like two different languages that can never translate into the exact same sentence. Because they can never be equal, the scale can never balance perfectly.

The Main Findings

1. The "Almost There" Trap
As the journey gets longer and longer (more steps), the ratio of "tripling" to "halving" gets incredibly close to a perfect balance. It's like a tightrope walker getting closer and closer to the center line.

The paper shows that as the sequence gets longer, the final number gets closer and closer to the starting number ( $F_q(m)/m \to 1$ ).
However, it never actually reaches 1. It gets infinitely close, but there is always a tiny, non-zero gap.

2. The "Finite" Barrier
Because the gap between the powers of 2 and 3 can never be zero, a "perfect loop" is mathematically impossible for any finite number of steps.

Analogy: Imagine trying to build a bridge with bricks that are slightly different sizes. You can get the ends very close together, but if the bricks are never the exact same size, you can never close the gap perfectly without a gap remaining.
Therefore, a "non-trivial cycle" (a loop that doesn't include the number 1) cannot exist.

3. The Only Safe Harbor
The paper concludes that the only time the process actually repeats is the trivial loop at the number 1 (1 $\to$ 4 $\to$ 2 $\to$ 1). Any other starting number will eventually break the pattern and head toward 1, rather than getting stuck in a different loop.

Summary

Daohang Sha uses a detailed map of "up" and "down" steps to show that while numbers in the Collatz game can get very close to forming a perfect loop, the fundamental math of powers of 2 and 3 makes it impossible for them to ever close the circle completely.

The takeaway: If you start with any number, you might get stuck in a very long, complicated dance, but you will never find a dance floor that circles back to the start without eventually stepping off the floor and landing on 1. The "infinite loop" is a mathematical impossibility.

Technical Summary: On the Bounds of Stopping and Cycle Numbers in the Collatz Process

Problem Statement
This paper addresses the 3n + 1 problem (Collatz conjecture), specifically focusing on the normalized Collatz iteration defined by $F_0(n) = n/2$ for even $n$ and $F_1(n) = (3n+1)/2$ for odd $n$ . The primary objective is to analyze the stopping time and cycle structure of this process. The author restricts the analysis to odd starting values $m \equiv 3 \pmod 4$ with a stopping time $s \ge 4$ , as smaller cases are trivially verifiable. The central question is whether finite nontrivial cycles (periodic orbits other than the trivial cycle at 1) can exist within this iteration.

Methodology
The paper employs a recursive description of admissible binary sequences to model the Collatz process. A sequence $q$ of length $s$ containing $r$ ones (representing odd steps) and $s-r$ zeros (representing even steps) is used to define the transformation $F_q(n)$ .

Key methodological components include:

Binary Sequence Representation: The transformation is expressed as $F_q(n) = \frac{3^r n + \sum_{i=1}^r 3^{r-i} 2^{l(i)-1}}{2^s}$ , where $l(i)$ denotes the position of the $i$ -th '1' in the sequence.
Recursive Tree Construction: The author introduces a modified rooted sequence tree (Figure 1) to generate admissible sequences. This tree is constructed by inserting specific substrings ("1" or "10") before the terminal block of zeros, ensuring a unique mapping between sequences and starting integers.
Number Theoretic Analysis: The paper utilizes properties of modular arithmetic (specifically modulo $2^s$ and modulo 4) and the uniqueness of binary expansions to establish a bijection between admissible sequences $q$ and integers $m \equiv 3 \pmod 4$ .
Inequality Derivation: By applying the Rearrangement Inequality, the author derives lower and upper bounds for the summation term $\sum_{i=1}^r 3^{r-i} 2^{l(i)-1}$ , which represents the additive component of the iteration.

Key Contributions and Results

Uniqueness of Representation (Theorem 2.10): The paper establishes a bijection between admissible binary sequences $q$ and integers $m \equiv 3 \pmod 4$ . Every such integer arises uniquely from a specific sequence in the constructed tree, and every sequence corresponds to a unique integer satisfying $F_q(m) < m$ .
Bounds on the Additive Term (Theorem 2.3 & 2.4): The summation term in the iteration formula is bounded. The minimum value is $3^r - 2^r$ (occurring when all '1's are at the start of the sequence), and the maximum value is attained when the '1's are distributed according to the logarithmic spacing of the sequence tree.
Non-Existence of Finite Nontrivial Cycles (Theorem 2.11 & 3.1):
- The paper proves that for any finite sequence, $F_q(4i-1) \neq 4i-1$ . A cycle would require the equality $2^s = 3^r$ , which is impossible for integers $s, r > 0$ .
- Consequently, no finite nontrivial cycle can occur. The only admissible periodic orbit is the trivial cycle at 1.
Asymptotic Behavior of the Ratio (Theorem 3.2): The paper derives bounds for the ratio $F_q(m)/m$ $F_{q} (m) / m$ . It shows that as the sequence length increases (and $r \to \infty$ $r \to \infty$ ), the ratio $3^r/2^s$ $3^{r} / 2^{s}$ approaches 1, but never equals 1.
- The ratio $F_q(m)/m$ is bounded by $1 - \epsilon_1 < F_q(m)/m < 1 + \epsilon_2$ .
- As $r \to \infty$ , $\lim F_q(m)/m \to 1$ .
Cycle Number Bounds: The paper provides lower and upper bounds for a hypothetical nontrivial cycle number $m_c$ . The lower bound is given by $m_c \ge \frac{3^r - 2^r}{2^s - 3^r}$ . For large $r$ (e.g., $r \approx 4.3 \times 10^{14}$ ), the lower bound is approximately $7.5 \times 10^{14}$ , while the upper bound is approximately $5.12 \times 10^{29}$ .

Significance and Claims
The paper claims to demonstrate that the structural requirements for a finite nontrivial cycle in the normalized Collatz iteration are unattainable. Specifically, the existence of such a cycle would necessitate an exact identity between powers of 2 and 3 ( $2^s = 3^r$ ), which is mathematically impossible.

The author concludes that:

The stopping time in the Collatz process admits no finite upper bound.
The ratio $F_q(m)/m$ approaches unity as the sequence length increases but never attains it for any finite sequence.
This structural obstruction, combined with the derived bounds, rules out the possibility of finite nontrivial cycles.
Therefore, the trivial cycle at 1 is the only admissible periodic orbit.

The paper relies on computational verification for small cases and theoretical bounds for large $r$ , noting that while the gap between $3^r$ and $2^s$ becomes infinitesimally small for large parameters (e.g., $1 - 3^r/2^s \approx 10^{-15}$ ), it remains strictly non-zero, preventing the formation of a cycle.