Collatz Conjecture Calculator (3n+1 Problem)

Collatz conjecture 3n+1 calculator: full trajectory, total stopping time, peak value, range analysis [1, N] and compressed version T(n) for efficient iteration.

Calculation parameters
Was this calculator useful?

The Collatz conjecture

The Collatz conjecture, also called 3n+1 problem, Syracuse conjecture or Ulam conjecture, is one of the most famous open problems in elementary mathematics. Formulated by Lothar Collatz in 1937, it states that for every positive integer n, repeated application of f(n) = n/2 if even, 3n+1 if odd, inevitably reaches 1. Despite apparent simplicity, a proof has eluded mathematicians for nearly a century.

The Collatz function

Formally:

f(n) = n/2 if n is even, 3n+1 if n is odd

The conjecture says for every n >= 1, the iterated sequence n, f(n), f(f(n)), ... eventually reaches 1, entering the cycle 1 -> 4 -> 2 -> 1. Example for n=27: 27, 82, 41, 124, 62, 31, 94, 47, 142, ... peak at 9232, finally reaching 1 after 111 steps.

Total stopping time

For integer n, T(n) = number of steps to reach 1. Examples: T(1)=0, T(2)=1, T(3)=7, T(4)=2, T(5)=5, T(6)=8, T(7)=16, T(27)=111, T(97)=118, T(871)=178. Empirical behavior shows chaotic oscillations: T(n) can vary enormously between consecutive integers. Conjecturally T(n) ~ (2/ln(4/3)) * ln(n) ~= 6.95 * ln(n) on average.

Computational verification

Verified for all n <= 2^68 ~ 2.95 * 10^20 (Barina 2021). No counterexample found: every tested n converges to 1. GPU-based verifications test ~10^12 numbers per second. This huge dataset strongly supports the conjecture but doesn't prove it: an astronomically large counterexample could exist.

Compressed version T(n)

A useful variant combines the odd step with the forced subsequent even step. If n is odd, 3n+1 is even, so one applies (3n+1)/2 directly. Compressed function:

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

Equivalent for the conjecture and produces trajectories about half the length. Used in computational tests for speed.

Five modes

  1. Trajectory: full sequence from n to 1 with peak and step count.
  2. Stopping time: T(n), iteration count.
  3. Peak: max value reached in trajectory (for n=27 it's 9232).
  4. Range analysis: statistics over [1, N] - average steps, max peaks.
  5. Compressed T(n): accelerated version with combined odd+even step.

Why is it so hard to prove?

Erdos famously said "mathematics is not yet ready for such problems". Difficulty stems from "chaotic" behavior: no obvious monotonicity, trajectories oscillate unpredictably. Tao (2019) proved "almost all" orbits (in asymptotic sense) decrease to small values, but "almost all" doesn't mean "all". Conway (1972) showed similar generalizations (3n+k variants) are Turing-complete, hinting at undecidability of the general form.

Partial results

  • Terras 1976: density of integers with finite stopping time is 1.
  • Krasikov-Lagarias 2003: at least x^(0.84) integers up to x reach 1.
  • Tao 2019: almost all orbits drop below any increasing function (improvement over Krasikov).
  • Conway 1972: Fractran generalization is Turing-complete, hence undecidable.
  • No nontrivial cycles for n <= 10^20.

Applications and connections

  • Computability theory: conjecture variants are equivalent to halting problem.
  • Discrete dynamics: paradigmatic deterministic chaotic system.
  • Number theory: links with 2-adic distributions and modular forms.
  • Cryptography: apparent randomness inspired pseudo-random generators.
  • Theoretical CS: benchmark for optimizers and compilers (deep recursion test).
  • Math education: accessible example of elementary open problem.

History of the Collatz conjecture

The conjecture is attributed to the German mathematician Lothar Collatz, who formulated it around 1937. Over the decades it has accumulated a remarkable number of names, a sign of how often it has been independently rediscovered: it is known as the 3n+1 problem, Ulam's conjecture, Kakutani's problem, Hasse's algorithm and the Syracuse problem. Its fame arises from the contrast between the extreme simplicity of its statement — take a number, if even halve it, if odd triple it and add one — and the impossibility of proving it. The great mathematician Paul Erdős, famous for his problems, declared that "mathematics is not yet ready for such problems" and offered a symbolic reward of 500 dollars to whoever solved it. Almost ninety years after its formulation, the conjecture remains open.

Modern verifications and attempts at proof

With computers, the conjecture has been verified for all numbers up to enormous values, beyond 2⁶⁸: no counterexample has ever been found, and every trajectory tested always reaches 1. But numerical verification, however extensive, is not a proof. On the theoretical front, in 1976 Riho Terras proved that almost all integers (in the sense of density) have a finite stopping time. The most recent and celebrated progress is by Terence Tao, who in 2019 proved that almost all Collatz orbits reach "almost bounded" values, the strongest partial result so far. Despite these advances and the enormous computational effort of distributed computing projects, a complete proof continues to elude mathematicians.

Updated July 2026

Frequently Asked Questions

What is the Collatz conjecture?

It is a mathematical conjecture about a simple iterative rule: starting from a positive integer, if it is even you divide it by two, if it is odd you multiply it by three and add one. The conjecture states that, whatever the starting number, repeating the operation always reaches 1. Despite the elementary statement, no one has yet managed to prove it or to find a counterexample.

What is the stopping time?

The total stopping time is the number of steps needed for the Collatz sequence, starting from an integer n, to reach the value 1. For example, starting from 6 it takes 8 steps. Some numbers have surprisingly long stopping times relative to their size: the famous 27 takes as many as 111 steps and rises up to 9232 before falling to 1. The study of these times is central to the statistical analysis of the conjecture.

Why is it so hard to prove?

The difficulty arises from the fact that the sequence mixes two operations of opposite nature: division, which reduces, and multiplication by three plus one, which increases. The alternation is chaotic and unpredictable, and there is no obvious algebraic structure or invariant that allows the long-term behaviour to be controlled. It is an example of a discrete dynamical system simple to define but with extremely complex behaviour, that defies current mathematical tools.

What is the compressed version T(n)?

It is a variant that merges two steps into one: when the number is odd, instead of computing 3n+1 (which is always even) and then dividing, you directly compute (3n+1)/2. This compressed version produces shorter but equivalent trajectories for the purposes of the conjecture: if one converges to 1, so does the other. It is often preferred in theoretical analysis because it removes the redundant even steps and simplifies the statistical estimates.

Has it been verified by computer?

Yes, massively. The conjecture has been verified for all integers up to enormous values, beyond 2⁶⁸, without ever finding a counterexample: every single trajectory tested reaches 1. Distributed computing projects keep extending this limit. However, however convincing, numerical verification does not constitute a proof: it always remains possible, in principle, that a counterexample larger than those tested exists.

What partial results exist?

In 1976 Riho Terras proved that almost all integers, in the sense of density, have a finite stopping time. In 2019 Terence Tao obtained the strongest result so far, proving that almost all Collatz orbits reach almost bounded values. These theorems do not prove the conjecture for every number, but they show that any exceptions would be extremely rare, reinforcing the belief that the conjecture is true.

Is the number 27 special?

Yes, it is the most famous example of surprising behaviour for a small number. Starting from 27, the Collatz sequence does not fall immediately but rises dramatically up to a peak of 9232, about 342 times the starting value, and takes 111 steps before reaching 1. It is the perfect illustration of how long and unpredictable the trajectory can be even starting from modest numbers.

Who formulated the Collatz conjecture?

It was the German mathematician Lothar Collatz who proposed it around 1937. Over time it has received many different names — the 3n+1 problem, Ulam's conjecture, the Syracuse problem, Hasse's algorithm — because it was independently rediscovered by various scholars. Paul Erdős, facing its resistance, said mathematics was not yet ready for such problems and offered 500 dollars to whoever solved it: the reward has never been claimed.

Comments (0)

No comments yet. Be the first!