Collatz (the 3n+1 problem)

Parent: number-theory · Dynamics-side view: orbit → collatz-orbit-statistics

Iterate T(n) = n/2 (if n even) or 3n+1 (if n odd), from any n ≥ 1. The conjecture: every orbit reaches 1 (then cycles 1→4→2→1). Open since ~1937; verified for all n < 2⁶⁸, no proof. Erdős: "mathematics is not yet ready for such problems."

Elementary observations:

• After 3n+1 (with n odd) the result is even, so a /2 always follows — people often study the "shortcut" map n ↦ (3n+1)/2.
• The hard part is there's no evident decreasing measure (well-founded rank) — values can climb far (e.g. 27 peaks at 9232) before falling. Without such a measure you can't run the usual termination argument (recursion-convergence-contraction).

Why it's so hard — a computability explanation

The 3n+1 map is one specific instance of a family that, as a family, is undecidable: Conway's generalized Collatz functions can simulate arbitrary computation, so "does the orbit reach 1?" has no general algorithm. Collatz sits inside that undecidable family — see generalized-collatz for the definition and the undecidability proof.

Caveat. The family being undecidable does not make this instance formally undecidable — a fixed instance is a definite (if unknown) truth. It explains the difficulty; it is not a proof that Collatz is unprovable.