Collatz Conjecture

The Collatz conjecture is a problem traditionally attributed to L. Collatz. Its exact date of origin is unclear, although Collatz traced its development to investigations of iterations of arithmetic functions begun during his student years from 1928 to 1933 (Lagarias 1985; Wirsching 1998, p. 11; Collatz 2010, pp. 241-245). It is also called the mapping, problem, Hasse's algorithm, Kakutani's problem, Syracuse algorithm, Syracuse problem, Thwaites conjecture, and Ulam's problem (Lagarias 1985). To state the conjecture, let be an integer and recursively define a sequence by

(1)

The Collatz conjecture states that this sequence eventually reaches 1 for every positive integer .

The members of the sequence produced by this process are sometimes known as hailstone numbers. Conway proved that the original Collatz conjecture has no nontrivial cycles of length . Lagarias (1985) showed that there are no nontrivial cycles with length . Conway (1972) also proved that Collatz-type problems can be formally undecidable. Kurtz and Simon (2007) proved that a natural generalization of the Collatz problem is undecidable; unfortunately, this proof cannot be applied to the original Collatz conjecture.

The following table summarizes reported computational verification limits for the Collatz conjecture.

starting values verified below	source
	Leavens and Vermeulen (1992)
	Vardi (1991, p. 129)
	Oliveira e Silva (2008)
	Barina (2025)
	Barina (2026)

Tao (2022) proved a strong almost-everywhere result: for every function tending to infinity, the Collatz orbit of reaches a value below for almost all positive integers in the sense of logarithmic density. This does not prove that every orbit reaches 1, but it shows that almost every orbit eventually falls below any prescribed slowly growing threshold.

Because of the difficulty in solving this problem, Erdős commented that "mathematics is not yet ready for such problems" (Lagarias 1985). Thwaites (1996) offered a £1000 reward for resolving the conjecture.

The following table gives the sequences obtained for the first few starting values (OEIS A070165).

	, , , ...
1	1
2	2, 1
3	3, 10, 5, 16, 8, 4, 2, 1
4	4, 2, 1
5	5, 16, 8, 4, 2, 1
6	6, 3, 10, 5, 16, 8, 4, 2, 1

The numbers of steps required for the algorithm to reach 1 for , 2, ... are 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, ... (OEIS A006577; illustrated above). Of these, the numbers of tripling steps are 0, 0, 2, 0, 1, 2, 5, 0, 6, ... (OEIS A006667), and the number of halving steps are 0, 1, 5, 2, 4, 6, 11, 3, 13, ... (OEIS A006666). The smallest starting values of that yields a Collatz sequence containing , 2, ... are 1, 2, 3, 3, 3, 6, 7, 3, 9, 3, 7, 12, 7, 9, 15, 3, 7, 18, 19, ... (OEIS A070167).

The Collatz conjecture can be implemented as an 8-register machine (Wolfram 2002, p. 100), quasi-cellular automaton (Cloney et al. 1987, Bruschi 2005), or 6-color one-dimensional quasi-cellular automaton with local rules but which wraps first and last digits around (Zeleny). In general, the difficulty in constructing true local-rule cellular automata arises from the necessity of a carry operation when multiplying by 3 which, in the worst case, can extend the entire length of the base- representation of digits (and thus require propagating information at faster than the CA's speed of light).

The Terras map was introduced by Terras (1976, 1979), who asked if iterating

(2)

always returns to 1 for initial integer value (e.g., Lagarias 1985, Cloney et al. 1987). This is simply the original statement above but combining the division by two into the addition step if is odd, thus compressing the number of steps. The following table gives the sequences for the first few starting values , 2, ... (OEIS A070168).

	, , ...
1	1
2	2, 1
3	3, 5, 8, 4, 2, 1
4	4, 2, 1
5	5, 8, 4, 2, 1
6	6, 3, 5, 8, 4, 2, 1
7	7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1

For the Terras map, if negative numbers are included, there are 4 known cycles: (1, 2), (), (, , ), and (, , , , , , , , , , ). It is a special case of the "generalized Collatz problem" with , , , , and . Terras (1976, 1979) also proved that the set of integers has a limiting asymptotic density , such that if is the number of such that and , then the limit

(3)

exists. Furthermore, as , so almost all integers have a finite stopping time. Finally, for all ,

(4)

where

			(5)
			(6)
			(7)

(Lagarias 1985).

The Matthews map generalizes this construction to a broader family of piecewise integer iterations, with analogous questions about cycles and divergence.