IDE
Sign in
Discrete dynamics Not a Millennium Prize Problem Status: Open Status last verified

Collatz Conjecture

Start with any positive integer. Halve it if it is even, otherwise triple it and add one. Does every starting value eventually reach 1?

Problem statement

Define T(n) = n/2 if n is even and T(n) = 3n + 1 if n is odd. Conjecture: for every positive integer n, some iterate T^k(n) equals 1.

T(n) = n / 2      (n even)
T(n) = 3n + 1     (n odd)

Conjecture: for every n ≥ 1 there is a k ≥ 0 with T^k(n) = 1.

Source: Jeffrey C. Lagarias — The 3x+1 problem and its generalizations

Introduction

The Collatz Conjecture (also called the 3x+1 problem) is named after Lothar Collatz. The rule is simple enough for a first programming exercise, yet nobody knows whether every starting value reaches 1.

It is not one of the Clay Millennium Prize Problems. It is a famous open problem because the rule mixes multiplication and division in a way that current methods cannot control for every starting value.

Computers have checked an enormous range of starting values, and every one of them reached 1. That is strong experimental evidence, but a finite check cannot rule out a counterexample further out: an orbit that grows forever, or a cycle other than 4 → 2 → 1.

Definitions

Orbit (trajectory)
The sequence n, T(n), T(T(n)), … obtained by applying the rule repeatedly.
Total stopping time
The number of steps an orbit needs to reach 1 (for 27 it is 111).
Counterexample
A starting value whose orbit never reaches 1: either it grows without bound, or it enters a cycle that does not contain 1.

What is known

Each statement says how certain it is: an established (proved) result, an experimental observation, an open conjecture, or an unverified claim.

  • Established result Almost all orbits attain almost bounded values: for any function f(n) tending to infinity, the minimum of the orbit of n is below f(n) for almost all n in the sense of logarithmic density. [Terence Tao]
  • Established result Generalizations of the 3x+1 rule can be undecidable (Conway, 1972) — a reason to expect the problem to be hard, not a result about this rule. [Jeffrey C. Lagarias]
  • Experimental observation Every starting value below 2^68 has been verified by computer to reach 1. [David Barina]
  • Open conjecture Every positive integer reaches 1 (the conjecture itself; unproven). [Jeffrey C. Lagarias]

Important limitations

  • Checking any finite range of starting values, however large, does not prove the conjecture.
  • Tao's result is about almost all starting values in a density sense; it does not exclude individual counterexamples.
  • Heuristic arguments (on average an odd step is followed by enough halvings to shrink the value) are not proofs.

Status history

  1. Status: Open Checked against the references below: no accepted proof or counterexample is known.

This status is maintained by the Zerethon IDE team from authoritative sources. Contributions, runs and AI answers never change it.