Collatz conjecture: definition, history, examples and significance

Definition and iteration rules

Formally, define a map T on the positive integers by T(n) = n/2 when n is even, and T(n) = 3n + 1 when n is odd. Iteration means forming the sequence n, T(n), T(T(n)), ... until a previously seen value appears. If the sequence reaches 1, it thereafter cycles through 1, 4, 2, 1. The rules are simple to state but produce complicated behavior for many starting values. A small example: starting with 6 the sequence goes 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, demonstrating a descent to the 1–4–2 cycle.

History and partial results

The problem was proposed by Lothar Collatz in 1937 and has attracted attention from both amateur and professional mathematicians. Extensive computational checks have shown the conjecture holds for an enormous range of starting values (computations have verified many billions and even ranges reported up to powers like 2^68), yet no complete proof or counterexample is known. Mathematicians have established various conditional and partial results: bounds on the density of potential counterexamples, properties of the so-called stopping time (how many steps until reaching a smaller value), and structural statements about possible cycles. However, the core statement — eventual reach of 1 for every positive integer — remains open.

Why the conjecture is difficult

The challenge arises from the process mixing multiplication and addition in a parity-dependent way. Even steps (division by two) shrink numbers, while odd steps (3n+1) usually increase them; the alternation between these effects depends sensitively on the pattern of bits in n. This nonlinearity resists classic techniques from algebra or analysis. Heuristic and probabilistic models suggest most numbers should decrease on average and eventually reach 1, but these heuristics do not amount to a rigorous proof. No other finite cycles besides the trivial 1–4–2 loop have been found, and no proof excludes long excursions to very large values before eventual descent.

Importance, applications, and cultural role

Although the Collatz conjecture does not appear to have practical applications, it serves as an accessible and compelling example of how simple rules can produce intricate and apparently unpredictable behavior. It has motivated work in computational mathematics, experimental number theory, and dynamical systems, and it is a popular topic in recreational mathematics and undergraduate study. Researchers use computational searches as testbeds for distributed computing and algorithmic optimizations; theoretical work connects the problem to ideas from ergodic theory, modular arithmetic, and randomness heuristics.

Notable facts and further reading

Key points to remember: the rule is elementary, only the 1–4–2 cycle is known, computations support the conjecture for extremely large ranges but do not substitute for proof, and the problem remains a simple-to-state example of a deep unsolved question. For introductions, historical notes, and current computational records see the following resources.

• Overview and formal statement
• Historical background and Collatz's original proposal
• Computational investigations and verified ranges
• Mathematical approaches and partial results
• Expository articles and problems for students