The Collatz conjecture

Does the 3n + 1 iteration reach 1 from every positive integer?

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Define $T:\mathbb{N}_{>0}\to\mathbb{N}_{>0}$ by

T(n) = \begin{cases} n/2, & n \text{ even},\\ 3n+1, & n \text{ odd}.\end{cases}

Is it true that for every $n \ge 1$ there exists $k$ with $T^{k}(n) = 1$ ?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Attributed to Lothar Collatz around 1937, and also known as the $3n+1$ problem, the Syracuse problem, and Kakutani's problem. Erdős is widely quoted as saying that mathematics is not yet ready for such problems.

Why it matters

The problem is a stress test for the boundary between arithmetic and dynamics: the map is elementary, but its orbits behave like a random walk, and no existing technique controls the interaction between the multiplicative and additive structure.

Known partial results

Verified computationally for all $n < 2^{68}$ .
Tao (2019) proved that almost all orbits attain almost bounded values: for any function $f$ diverging to infinity, $T$ -orbits of almost all $n$ (in logarithmic density) reach a value below $f(n)$ .
Conway showed that natural generalisations of the iteration are undecidable, which suggests the specific arithmetic of $3n+1$ matters.

References

[1]T. Tao, Almost all orbits of the Collatz map attain almost bounded values, Forum of Mathematics Pi 10 (2022). link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.