Collatz sequence (3n+1)

The Collatz sequence, or 3n+1 problem, is defined by iterative rule: given positive integer n, if n is even let n -> n/2; if n is odd let n -> 3n+1. Collatz conjecture states that starting from any n, sequence always reaches 1 after finite steps.

Formal definition

f(n) = n/2 if n even, f(n) = 3n+1 if n odd. Collatz sequence from n_0 is n_0, n_1 = f(n_0), .... Example n=6: 6, 3, 10, 5, 16, 8, 4, 2, 1 (8 steps). Example n=27: 27, 82, 41, ..., 9232 (max), ..., 1 (111 steps).

Collatz conjecture

Lothar Collatz (1937): for every n >= 1, sequence reaches 1 in finite steps. Also known as 3n+1 problem, Ulam problem, Kakutani problem. Erdos: "Mathematics is not yet ready for this problem." Erdos offered $500 for proof.

Empirical verification

Conjecture verified computationally for all n < 2^68 ~ 2.95 * 10^20 (Tomas Oliveira e Silva, Roosendaal, 2020). However numerical evidence is not proof: even if true for first billions, may fail for huge counterexample. Polya conjecture failed at 906 million; Mertens conjecture failed at 10^14.

Stopping times

• Total stopping time: iterations to reach 1.
• Stopping time: first step k where n_k < n_0.
• For n=27: total = 111, stopping time = 96.
• Empirical average: total ~ 6.95 ln(n) (heuristic).

Record numbers

n with total stopping time greater than all n' < n. OEIS A006877: 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, ...

Maxima reached

n_max = max in sequence from n. For n = 27: n_max = 9232 (~ 342 * n). For n = 703: n_max = 250504 (~ 356 * n). Growth ~ n * (fluctuating value), suggesting "random" behavior.

Probabilistic aspects

For random n, sequence has random aspects. Heuristic: per step, probability of doubling ~ 1/2. Geometric mean per odd-even cycle ~ (3/2)^(1/2) * (1/2)^... ~ 0.75. So sequence decreases on average. Heuristically explains why all reach 1.

Generalizations

• 5n+1 variant: sequence may grow unboundedly (e.g., n=7 cycles).
• 7n+1: different behavior, some cycles.
• Generalized cycles: beyond 1 -> 4 -> 2 -> 1? Open.
• Collatz on Z (negative): cycles known on -1, -5, -7, -17.
• Polynomial Collatz, on Q[x]: recent studies.

Partial results

• Terras (1976): almost all n have stopping time < n^0.869.
• Krasikov-Lagarias (2003): density 0 for "non-converge".
• Tao (2019): "almost all" Collatz orbits reach arbitrarily small values.
• Conway (1972): Collatz generalization undecidable in abstract.

Applications

• Dynamical systems theory: nonlinear dynamics on Z.
• Complexity theory: "unpredictable" simple functions.
• Algorithms and benchmarking: deep sequence tests.
• Math education: introduction to open problems.
• Theoretical cryptography: Collatz-based hash (experimental).

History

Lothar Collatz (1937) introduces problem studying directed graphs. Stanislaw Ulam, Bryan Thwaites independently rediscover. Hasse, Kakutani contribute. Coxeter, Erdos popularize. Lagarias (1985) classic review. Oliveira e Silva (2008-2020) computational verification. Tao (2019) best partial result.

Why it is undecidable in general: Conway's functions

One of the deep reasons the Collatz conjecture resists is that a natural generalization of it is provably undecidable. In 1972 John Conway studied generalized Collatz-type functions, in which the multiplier and the addend depend on the residue of n modulo a fixed integer. Conway proved that such maps can simulate any Turing machine: his FRACTRAN language, based precisely on iterations of this kind, is Turing-complete.

It follows that there can be no general algorithm that, given a Collatz-type function, decides whether all orbits reach 1: it would be equivalent to solving the halting problem, notoriously undecidable. This does not prove that the specific 3n+1 case is undecidable, but it explains why general tools fail: the Collatz problem lives at the boundary between number theory, dynamical systems and computability, where small variations of the rules produce arbitrarily complex behaviour.

Tao's result (2019) and the 2-adic structure

The most significant progress toward the conjecture came in 2019 from Terence Tao, who proved a statement very close to it: almost all Collatz orbits reach arbitrarily small values. More precisely, for almost every n (in the sense of logarithmic density) the sequence drops below any function that tends to infinity, however slowly. It is not the full conjecture, but the strongest statistical result known, obtained with probability-theory techniques applied to the iterations.

A fruitful viewpoint regards the 3n+1 map as a dynamical system on the 2-adic integers, where the divisibility-by-two structure becomes natural geometry. In this framework the iterations resemble a random walk with negative drift: on average each step multiplies the number by about 3/4, suggesting the descent toward 1. But "on average" is not enough to guarantee that no orbit escapes, and it is precisely this jump from the probabilistic to the certain that is the still-unsolved heart of the problem.

Updated July 2026