The Collatz Conjecture: A Problem You Can State in Three Lines and Nobody Can Solve

0. Key points

• The rule takes only two lines. Given a natural number $n$, replace it by $n/2$ if it is even and by $3n+1$ if it is odd. Repeat, and you will always reach $1$ — that is the Collatz conjecture, open since it was posed in the 1930s.
• Small numbers drop to $1$ almost at once. But starting from $27$ takes $111$ steps and the orbit climbs as high as $9232$ along the way. This single example teaches us that “simple” is not the same as “easy”.
• It is not true that nothing is known. Statements such as “no cycle containing exactly one or exactly two odd numbers exists apart from the trivial one” and “at least three quarters of all natural numbers fall below their starting value within three steps” are proved in full in this article.
• The reason the conjecture is believed to be true is a probabilistic estimate: on average each step shrinks the number by a factor of $\sqrt{3/4} \approx 0.866$. That, however, is not a proof.
• Changing $3n+1$ to $3n-1$ produces a counterexample ($5 \to 14 \to 7 \to 20 \to 10 \to 5$). A correct proof must therefore be delicate enough to distinguish "$+1$" from "$-1$", and that is the central obstacle.

1. Motivation: an open problem whose rules fit in three lines

With most open problems in mathematics, merely understanding the statement is already work. To explain the Riemann hypothesis to someone, we must begin with complex numbers and the zeta function.

The Collatz conjecture is not like that. Here is the entire rule.

1. Pick a natural number.
2. If it is even, divide it by $2$. If it is odd, multiply by $3$ and add $1$.
3. Return to step 2.

And here is the conjecture: whatever natural number we start from, we eventually reach $1$.

A child can play this game. Let us start from $6$.

$$6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$

We land after $8$ steps. Once at $1$ the sequence cycles $1 \to 4 \to 2 \to 1$ forever, so we stop there.

The problem is attributed to the German mathematician Lothar Collatz, who is said to have posed it around 1937. Since then it has acquired many names — the Kakutani problem after Shizuo Kakutani, and associations with Ulam, Hasse and Thwaites — and it is also called the Syracuse problem or the $3n+1$ problem. A profusion of names means a profusion of people independently obsessed with it.

Paul Erdős is reported to have offered a prize of 500 dollars for the problem while remarking, in effect, that mathematics is not yet ripe for questions of this kind. In 2021 a Japanese company made news by offering a prize of 120 million yen. It is still unsolved.

Caution

This problem has a dangerous charm: it feels as though a little thought ought to settle it. Number theorists are quite used to receiving “proofs” of the Collatz conjecture in the mail. By the end of this article we hope it will be clear why every naive strategy fails.

2. Preliminaries: the Collatz map, orbits, stopping time

To turn the game into mathematics we fix some vocabulary. Throughout, $\mathbb{N} = \{1, 2, 3, \ldots\}$, so $0$ is excluded.

Definition 2.1（The Collatz map）

Define a map $C : \mathbb{N} \to \mathbb{N}$ by

$$C(n) = \begin{cases} n/2 & (n \text{ even}) \\ 3n+1 & (n \text{ odd}) \end{cases}$$

We call $C$ the Collatz map.

When $n$ is odd, $3n+1$ is necessarily even, so an odd number is always followed by an even one. It is therefore convenient to package “apply $3n+1$ and immediately halve” into a single step.

Definition 2.2（The shortcut Collatz map）

Define a map $T : \mathbb{N} \to \mathbb{N}$ by

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

We call $T$ the shortcut Collatz map.

Each step of $T$ is one or two steps of $C$, so reaching $1$ under $C$ and reaching $1$ under $T$ are equivalent. In proofs we use whichever makes the computation shorter.

Definition 2.3（Orbit, stopping time, cycle）

For $n \in \mathbb{N}$, the sequence $n,\, C(n),\, C^2(n),\, \ldots$ is called the orbit of $n$.

The quantity

$$\sigma(n) = \min\{\, k \ge 1 : C^k(n) < n \,\}$$

is called the stopping time of $n$ (if no such $k$ exists we set $\sigma(n) = \infty$).

Furthermore, if there is a $k \ge 1$ with $C^k(m) = m$, the finite set $\{m, C(m), \ldots, C^{k-1}(m)\}$ containing $m$ is called a cycle.

The stopping time answers “how many steps until we fall below the starting value?”. It is easier to handle than the number of steps needed to reach $1$ (the total stopping time), and as we shall see it already suffices to restate the conjecture.

flowchart LR
A["natural number n"] --> B{"is n even?"}
B -- "yes" --> C["replace by n / 2"]
B -- "no" --> D["replace by 3n + 1"]
C --> E{"is n = 1?"}
D --> E
E -- "no" --> A
E -- "yes" --> F["stop"]

One step of the Collatz map

3. Getting our hands dirty first

Before theory, let us look at some numbers.

Example 3.1（A report card for 1 through 12）

For each $n$ we list the number of steps needed to reach $1$ (the total stopping time) and the maximum value attained along the orbit.

$n$	steps	orbit maximum
1	0	1
2	1	2
3	7	16
4	2	4
5	5	16
6	8	16
7	16	52
8	3	8
9	19	52
10	6	16
11	14	52
12	9	16

For instance the orbit of $7$ is

$$7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$

which indeed takes 16 steps and peaks at $52$. Neighbouring values behave completely differently: $6$ and $7$ take $8$ and $16$ steps, $8$ and $9$ take $3$ and $19$. This irregularity is the essence of the problem.

Example 3.2（27, the troublemaker）

Starting from $27$, the orbit sets off like this.

$$27 \to 82 \to 41 \to 124 \to 62 \to 31 \to 94 \to 47 \to 142 \to 71 \to 214 \to 107 \to \cdots$$

It falls, then climbs again, over and over; it reaches a maximum of $9232$ and finally lands on $1$ after $111$ steps. The starting point $27$ has two digits. It climbs to four.

Its neighbours are tame: $26$ finishes in $10$ steps, $28$ in $18$. Only $27$ stands out, and the intuition that “a small number should take few steps” is destroyed here once and for all.

Tracing orbits by hand is laborious, so let us hand the work to a program. The following code uses only the standard library.

def total_stopping_time(n):
    """Return the number of steps for n to reach 1 and the orbit maximum."""
    steps, peak = 0, n
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        peak = max(peak, n)
        steps += 1
    return steps, peak

print(total_stopping_time(27))   # (111, 9232)
print(max(range(1, 10**6), key=lambda n: total_stopping_time(n)[0]))
# 837799 (the number below one million with the most steps: 524)

The last line returns $837799$, whose orbit takes $524$ steps. Is “at most $524$ steps among all numbers below one million” surprisingly small? Or is it ”$524$ steps of wandering with no guarantee of ever landing”? Both reactions are correct, and that is part of what makes this problem delightful.

4. What can be proved straight from the definition

It is not the case that nothing is known. Here are three facts we can prove with pencil and paper.

Theorem 4.1（Powers of two are well behaved）

For every integer $k \ge 0$ we have $C^k(2^k) = 1$; that is, $2^k$ reaches $1$ in exactly $k$ steps.

Proof（Theorem 4.1）

We argue by induction on $k$. For $k = 0$ we have $2^0 = 1$ and $C^0(1) = 1$, so the claim holds.

Assume the claim for $k$. Since $2^{k+1}$ is even, Definition 2.1 gives $C(2^{k+1}) = 2^{k+1}/2 = 2^k$. Hence

$$C^{k+1}(2^{k+1}) = C^{k}\bigl(C(2^{k+1})\bigr) = C^k(2^k) = 1$$

where the last equality is the induction hypothesis. This proves the claim for $k+1$.

∎

So $2, 4, 8, 16, 32, \ldots$ drop in a straight line. Numbers as docile as these are not the source of the difficulty.

Proposition 4.2（Numbers congruent to 1 mod 4 shrink within three steps）

If $n$ is even then $\sigma(n) = 1$. If $n \ge 5$ satisfies $n \equiv 1 \pmod 4$ then $\sigma(n) = 3$, and moreover

$$C^3(n) = \frac{3n+1}{4} .$$

Consequently the proportion (in the sense of natural density) of natural numbers with $\sigma(n) \le 3$ is at least $3/4$.

Proof（Proposition 4.2）

If $n$ is even then Definition 2.1 gives $C(n) = n/2 < n$, so $\sigma(n) = 1$.

Next let $n \equiv 1 \pmod 4$ with $n \ge 5$, and write $n = 4k+1$ with $k \ge 1$. Since $n$ is odd,

$$C(n) = 3(4k+1)+1 = 12k+4 .$$

This is even, so $C^2(n) = 6k+2$, which is again even, so $C^3(n) = 3k+1$. Now

$$\frac{3n+1}{4} = \frac{12k+3+1}{4} = 3k+1$$

which confirms the stated identity.

Let us check that $\sigma(n) = 3$. First, $C^3(n) = 3k+1 < 4k+1 = n$ follows from $k \ge 1$. On the other hand no shrinkage occurs at the two intermediate steps: indeed $C(n) = 12k+4 > 4k+1 = n$ (because $8k+3 > 0$) and $C^2(n) = 6k+2 > 4k+1 = n$ (because $2k+1 > 0$). Hence the first time we drop below $n$ is exactly $3$.

Finally we count densities. Among the natural numbers from $1$ to $N$, roughly $N/2$ are even and roughly $N/4$ are congruent to $1$ modulo $4$, and the two families do not overlap. So at least about $N/2 + N/4 = 3N/4$ of them satisfy $\sigma(n) \le 3$, and letting $N \to \infty$ gives a proportion of at least $3/4$.

∎

This computation suggests a thought: if we work with finer residues, perhaps we can catch more values of $n$. That is exactly what happens. For the congruence notation $a \equiv b \pmod m$, used here and below, see the definition of congruence（Definition 3.2）［Why Mathematics Is Hard］.

Example 4.3（Numbers congruent to 3 mod 16 also fall）

Let $n \equiv 3 \pmod{16}$, that is, $n = 16k+3$ with $k \ge 0$. Apply $C$ six times.

$$16k+3 \to 48k+10 \to 24k+5 \to 72k+16 \to 36k+8 \to 18k+4 \to 9k+2$$

The final value $9k+2$ is smaller than $16k+3$ (the difference is $7k+1 > 0$), so $\sigma(n) \le 6$. The numbers with $n \equiv 3 \pmod{16}$ make up $1/16$ of all natural numbers, and they overlap neither the even numbers nor the numbers $1 \bmod 4$ caught by Proposition 4.2 (a number that is $3 \bmod 16$ is an odd number that is $3 \bmod 4$). Together the proportion rises to at least $1/2 + 1/4 + 1/16 = 13/16$.

Pushing this procedure through modulo $2^k$ for every $k$ yields the following theorem.

Remark 4.4

Terras (R. Terras, 1976) proved that the set of $n$ with $\sigma(n) < \infty$ has natural density $1$. In other words, “almost every natural number does eventually fall below itself” is known. This is the argument of Proposition 4.2 and Example 4.3 carried out modulo $2^k$ and pushed to $k \to \infty$. Note, however, that density $1$ does not mean “finitely many exceptions”: an infinite set of exceptions can still have density $0$.

That it suffices to control stopping times is justified by the following reformulation.

Theorem 4.5（Reformulation via stopping time）

The following two statements are equivalent.

(a) For every $n \in \mathbb{N}$ the orbit of $n$ contains $1$ (the Collatz conjecture).

(b) For every $n \ge 2$ we have $\sigma(n) < \infty$.

Proof（Theorem 4.5）

(a) $\Rightarrow$ (b). Let $n \ge 2$. By (a) there is a $k \ge 0$ with $C^k(n) = 1$. Since $n \ge 2 > 1$ we must have $k \ge 1$, and $C^k(n) = 1 < n$. Thus at least one time at which the orbit drops below $n$ exists, and the least such time $\sigma(n)$ is finite.

(b) $\Rightarrow$ (a). We prove “the orbit of $n$ contains $1$” by strong induction on $n$.

For $n = 1$ the first term of the orbit is $1$, so the claim holds.

Let $n \ge 2$ and assume the claim for every natural number smaller than $n$. By (b) the number $k = \sigma(n)$ is finite; put $m = C^k(n)$, so that $m < n$ and $m \ge 1$. By the induction hypothesis the orbit of $m$ contains $1$, so $C^j(m) = 1$ for some $j \ge 0$. Then

$$C^{k+j}(n) = C^j\bigl(C^k(n)\bigr) = C^j(m) = 1$$

so the orbit of $n$ contains $1$ as well.

∎

Tip

Theorem 4.5 replaces the problem of “tracking an orbit out to infinity” by the problem of “does it ever drop, even once, in finitely many steps?”. Reductions of this kind — turning a statement about the infinite into a statement about the finite — appear everywhere in mathematics.

5. The danger of going round in circles: do cycles exist?

If the conjecture fails, it can fail in only two ways.

1. The orbit of some $n$ enters a cycle not containing $1$.
2. The orbit of some $n$ grows without bound (diverges to positive infinity（Definition 5.2）［Why You Cannot Divide by Zero］).

About the first possibility, a good deal can be proved.

Lemma 5.1（Every cycle contains an odd number）

Every cycle of $C$ contains at least one odd number.

Proof（Lemma 5.1）

Suppose a cycle $\{m, C(m), \ldots, C^{k-1}(m)\}$ consists entirely of even numbers. Then by Definition 2.1 each term is half the previous one, so $C^k(m) = m/2^k$. By the definition of a cycle, $C^k(m) = m$, whence $m = m/2^k$, that is, $m(2^k - 1) = 0$. Since $k \ge 1$ we have $2^k - 1 \ge 1$, so $m = 0$, contradicting $m \in \mathbb{N}$.

∎

List the odd numbers occurring in a cycle in order as $n_1, n_2, \ldots, n_r$ (pairwise distinct). If $n_i$ is odd then $3n_i + 1$ is even, and we keep halving as long as the result is even until we arrive at the next odd number $n_{i+1}$ (reading the index after $r$ as $1$). Writing $a_i \ge 1$ for the number of halvings, we obtain

$$3 n_i + 1 = 2^{a_i} n_{i+1} \qquad (i = 1, \ldots, r) .$$

This relation is the starting point for the study of cycles.

Theorem 5.2（Cycles with at most two odd numbers）

The only cycle of $C$ containing exactly one or exactly two odd numbers is $\{1, 4, 2\}$.

Proof（Theorem 5.2）

By Lemma 5.1 there is at least one odd number. We use the relation derived above.

Case of one odd number. If $r = 1$ we read $n_2 = n_1 = n$ and get $3n + 1 = 2^a n$, that is,

$$n (2^a - 3) = 1 .$$

Both $n$ and $2^a - 3$ are integers with product $1$, and $n \ge 1$, so $n = 1$ and $2^a - 3 = 1$, i.e. $2^a = 4$ and $a = 2$. The cycle is then $1 \to 4 \to 2 \to 1$, which as a set is $\{1, 4, 2\}$.

Case of two odd numbers. Suppose distinct odd numbers $n_1 \ne n_2$ satisfy

$$3n_1 + 1 = 2^{a_1} n_2, \qquad 3n_2 + 1 = 2^{a_2} n_1 .$$

Multiplying the two equations and setting $A = a_1 + a_2 \ge 2$ gives

$$(3n_1+1)(3n_2+1) = 2^{A} n_1 n_2 ,$$

and expanding the left-hand side,

$$9 n_1 n_2 + 3(n_1 + n_2) + 1 = 2^A n_1 n_2 ,$$

that is,

$$(2^A - 9)\, n_1 n_2 = 3(n_1 + n_2) + 1 .$$

The right-hand side is positive, hence so is the left, giving $2^A > 9$. The smallest power of $2$ exceeding $9$ is $16$, so $2^A \ge 16$ and therefore $2^A - 9 \ge 7$. Since $n_1 n_2 > 0$,

$$7 n_1 n_2 \le (2^A - 9)\, n_1 n_2 = 3(n_1 + n_2) + 1 .$$

Without loss of generality assume $n_1 < n_2$ (they are distinct, so equality cannot occur).

If $n_1 = 1$, the inequality becomes $7 n_2 \le 3 + 3 n_2 + 1$, that is, $4 n_2 \le 4$ and so $n_2 \le 1$. This contradicts $n_2 > n_1 = 1$.

If $n_1 \ge 3$ (the next odd number after $1$ is $3$), we bound the left-hand side from below by $7 n_1 n_2 \ge 21 n_2 = 3 n_2 + 18 n_2$. On the other hand $n_2 > n_1 \ge 3$ gives $18 n_2 > 18 n_1 \ge 3 n_1 + 1$ (since $15 n_1 \ge 45 > 1$). Therefore

$$7 n_1 n_2 \ge 3 n_2 + 18 n_2 > 3 n_2 + 3 n_1 + 1 = 3(n_1+n_2) + 1$$

contradicting the inequality above.

Hence no cycle with two odd numbers exists, and the only cycle is $\{1,4,2\}$.

∎

The argument becomes drastically harder as the number $r$ of odd numbers grows, but research proceeds by sharpening the same relation. It is now known that any cycle not containing $1$ would have to be far longer than a billion steps.

flowchart LR
n12["12"] --> n6["6"] --> n3["3"] --> n10["10"] --> n5["5"] --> n16["16"] --> n8["8"] --> n4["4"] --> n2["2"] --> n1["1"]
n80["80"] --> n40["40"] --> n20["20"] --> n10
n13["13"] --> n40
n21["21"] --> n64["64"] --> n32["32"] --> n16
n128["128"] --> n64

Numbers flowing into 1 (arrows are single steps)

If we extend the branches of this picture indefinitely, does every natural number appear in this single tree? That is the Collatz conjecture. Looking at the diagram, $16$ receives two inflows, from $32$ and from $5$, and $40$ receives two, from $80$ and from $13$. Every even number $m$ receives $2m$, and when $m \equiv 4 \pmod 6$ it also receives the odd number $(m-1)/3$. The tree spreads upward exponentially (for a vivid illustration of how fast exponential growth is, see the story of folding paper 42 times（Example 6.1）［Why Mathematics Is Hard］), so checking whether it exhausts everything is far harder than the picture makes it look.

6. Why is it believed to be true?

There is no proof, yet most mathematicians believe the Collatz conjecture. The reason is the following estimate.

Applying the shortcut map Definition 2.2 to an odd number $n$ gives $(3n+1)/2 \approx 1.5 n$, while applying it to an even number gives $0.5 n$. Suppose we assume that “the parities of the numbers appearing along an orbit are as random as coin flips”. Then the geometric mean of the multiplier per step is

$$\sqrt{1.5 \times 0.5} = \sqrt{0.75} \approx 0.866$$

which is less than $1$. So a typical orbit, rising and falling, should on average shrink by about 13% per step. If it keeps shrinking it must eventually land on a small number, and once it does, the induction of Theorem 4.5 takes over.

The estimate even predicts the number of steps. Working with $C$, each odd number is followed on average by two halvings (the probability that $3n+1$ is exactly divisible by $2^j$ is $2^{-j}$, so the expected value is $2$), so with $k$ odd numbers and $2k$ even ones the overall multiplier is $3^k / 2^{2k} = (3/4)^k$. This equals $1/n$ when $k = \ln n / \ln(4/3)$, so the total number of steps is predicted to be $3k \approx 10.4 \ln n$. For $n$ around one million this gives $10.4 \times 13.8 \approx 144$ steps, and the measured values do cluster near there. Not a bad prediction.

Caution

Nevertheless this is not a proof (recall what a proof is（Definition 4.1）［Why Mathematics Is Hard］), because there is no justification for the assumption that the parities along an orbit are random. The orbit is determined deterministically; nobody is flipping coins. Remember that $27$ took $111$ steps and climbed to $9232$ (Example 3.2). Events that would be rare under randomness do in fact occur. A probabilistic argument can say how rare the exceptions are; it can never say that there are none.

The best results that have been proved lie in the direction of making this probabilistic intuition rigorous. In 2019 Terence Tao showed that for any function $f$ with $f(n) \to \infty$, the orbit of almost every $n$ attains a value below $f(n)$. So we have reached “almost every $n$ does at some point become very small”. Between that and “every $n$ reaches $1$” a deep gulf remains.

7. Why it is hard: the cruel counterexample 3n−1

Here is the sharpest illustration of why naive strategies fail. Change the $+1$ in the rule to $-1$.

Proposition 7.1（The 3n−1 version has a nontrivial cycle）

Define $D : \mathbb{N} \to \mathbb{N}$ by $D(n) = n/2$ if $n$ is even and $D(n) = 3n - 1$ if $n$ is odd. Then, besides $\{1, 2\}$, the map $D$ has the cycle

$$5 \to 14 \to 7 \to 20 \to 10 \to 5 .$$

Proof（Proposition 7.1）

We compute step by step. Since $5$ is odd, $D(5) = 3 \cdot 5 - 1 = 14$. Since $14$ is even, $D(14) = 7$. Since $7$ is odd, $D(7) = 3 \cdot 7 - 1 = 20$. Since $20$ is even, $D(20) = 10$, and since $10$ is even, $D(10) = 5$. Hence $D^5(5) = 5$, so $\{5, 14, 7, 20, 10\}$ is a cycle. It does not contain $1$, so it differs from $\{1,2\}$.

Note also that $D(1) = 2$ and $D(2) = 1$, so $\{1,2\}$ is a cycle too.

∎

This is where the difficulty bites. The probabilistic estimate of Section 6 is completely unchanged if we replace $+1$ by $-1$ (since $3n-1 \approx 3n$). In other words, the argument “it shrinks on average, hence it falls to $1$” reaches the same conclusion for a problem that has a counterexample. As it stands, therefore, this strategy can never constitute a proof.

Example 7.2（Allowing negative numbers makes matters worse）

The cycle above is not the only one for $D$. The sequence

$$17 \to 50 \to 25 \to 74 \to 37 \to 110 \to 55 \to 164 \to 82 \to 41 \to 122 \to 61 \to 182 \to 91 \to 272 \to 136 \to 68 \to 34 \to 17$$

is also a cycle (verify each step exactly as in Proposition 7.1).

Moreover, under the substitution $n \mapsto -n$ the map $D$ becomes the original Collatz map $C$. So if we extend $C$ to the negative integers, three cycles appear: $-1 \to -2 \to -1$, then $-5 \to -14 \to -7 \to -20 \to -10 \to -5$, and finally a cycle of length $18$ starting from $-17$. The formula defining $C$ is the same on both sides of zero, and yet on the positive side there is (conjecturally) only one cycle. No one has found an explanation for this asymmetry.

There is one more warning, from a deeper source. In 1972 John Conway considered a family of maps generalizing the Collatz map, in which a separate linear expression is applied according to the residue of $n$ modulo $m$, and showed that no general algorithm can decide whether a given starting point reaches $1$ (the question is algorithmically undecidable). This does not say that the Collatz conjecture itself is undecidable, but the fact that “there is no universal method for problems of this kind” has been proved is a weighty one.

Remark 7.3（The state of computational verification）

Computer verification has confirmed that every natural number up to $2^{68} \approx 2.95 \times 10^{20}$ reaches $1$ (Barina, 2021). That is an enormous range, and yet it is nothing compared with infinity. Indeed, if the smallest counterexample were lurking somewhere around $10^{100}$, the present verification would exclude it not at all. That no amount of finite checking amounts to a proof is shown bluntly by the formula that works 40 times and fails on the 41st（Example 4.2）［Why Mathematics Is Hard］.

On the theoretical side, it has been shown, for example, that the number of natural numbers up to $x$ that reach $1$ is at least $x^{0.84}$ (Krasikov–Lagarias, 2003). Since $x^{0.84}$ is far smaller than $x$, this shows how difficult it is even to count “almost all” of them.

8. Exercises

Exercise 8.1Easy

Let $C$ be the map of Definition 2.1. Write down the orbit of $n = 9$, and find the number of steps needed to reach $1$ together with the orbit maximum.

Solution

We compute in order.

$$9 \to 28 \to 14 \to 7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$

Counting $9$ as term number $0$, the value $1$ is term number $19$. Hence the number of steps is $19$. The maximum is $52$.

In the table of Example 3.1, $7$ took $16$ steps, and the orbit above falls to $7$ after three steps: $3 + 16 = 19$, in agreement. This “once you merge into a number you have already computed, there is no need to recompute” is the basic technique for evaluating Collatz sequences quickly.

Exercise 8.2Standard

Let $n$ be odd. Check that $4n+1$ is odd as well, and then prove

$$C^3(4n+1) = C(n) .$$

What does this mean? Verify it in the case $n = 5$.

Solution

If $n$ is odd then $4n$ is even, so $4n+1$ is odd. Hence

$$C(4n+1) = 3(4n+1) + 1 = 12n + 4 .$$

This is even, so $C^2(4n+1) = 6n + 2$, which is again even, so

$$C^3(4n+1) = 3n + 1 .$$

On the other hand $n$ is odd, so $C(n) = 3n+1$. The two agree.

In other words, the orbit of $4n+1$ merges into the orbit of $n$ after three steps.

For $n = 5$ we have $4n+1 = 21$. Indeed $21 \to 64 \to 32 \to 16$, and $C(5) = 16$, so the orbits do merge. This fact corresponds to the way $21$ flowed through $64$ into $16$ in the diagram after Theorem 5.2. Since for an odd $n$ the numbers $n, 4n+1, 4(4n+1)+1 = 16n+5, \ldots$ all merge at the same place, the Collatz tree contains infinitely many “look-alike” branches.

Exercise 8.3Standard

Show that a number $n$ with $n \equiv 11 \pmod{16}$ does not become smaller than $n$ within the same six steps used in Example 4.3.

Solution

Put $n = 16k + 11$ with $k \ge 0$ and compute. Since $n$ is odd,

$$C(n) = 48k + 34 .$$

This is even, so $C^2(n) = 24k + 17$, which is odd, so $C^3(n) = 72k + 52$; this is even, so $C^4(n) = 36k + 26$, again even, so $C^5(n) = 18k + 13$, which is odd, so

$$C^6(n) = 54k + 40 .$$

Since $54k + 40 > 16k + 11$ (the difference is $38k + 29 > 0$), no shrinkage has occurred in six steps. That all the intermediate values also exceed $16k+11$ is checked in the same way one by one, for instance $C^5(n) = 18k+13 > 16k+11$ (difference $2k+2 > 0$).

Thus the procedure of Example 4.3 succeeds for some residue classes and fails for others, and the failures must be re-examined by splitting further, modulo $32$, modulo $64$, and so on. Terras’s theorem in Remark 4.4 asserts that if this refinement is continued indefinitely, the proportion of the ones left behind tends to $0$.

Exercise 8.4Hard

Let $T$ be the shortcut Collatz map of Definition 2.2. Prove by induction on $k$ that for $k \ge 0$ and $m \ge 1$,

$$T^k(2^k m - 1) = 3^k m - 1 .$$

Use this to explain why numbers of the form $n = 2^k - 1$ grow considerably at first.

Solution

Case $k = 0$. The left-hand side is $T^0(m - 1) = m - 1$ and the right-hand side is $m - 1$; they agree.

Assume the claim for $k$ and prove it for $k+1$. Put $N = 2^{k+1} m - 1$. Since $2^{k+1} m$ is even (because $k + 1 \ge 1$), $N$ is odd. Hence by Definition 2.2,

$$T(N) = \frac{3(2^{k+1} m - 1) + 1}{2} = \frac{3 \cdot 2^{k+1} m - 2}{2} = 3 \cdot 2^{k} m - 1 = 2^k (3m) - 1 .$$

This has the form $2^k m' - 1$ with $m' = 3m \ge 1$, so the induction hypothesis applies and

$$T^{k+1}(N) = T^k\bigl(T(N)\bigr) = T^k(2^k m' - 1) = 3^k m' - 1 = 3^k \cdot 3m - 1 = 3^{k+1} m - 1 .$$

This completes the induction.

Interpretation. Taking $m = 1$, the number $n = 2^k - 1$ becomes $3^k - 1$ after $k$ shortcut steps. The multiplier is roughly $(3/2)^k$, and the larger $k$ is, the more violent the growth. The probabilistic estimate of Section 6 gave “an average factor of $0.866$ per step”, but for numbers of this form the first $k$ steps are all odd steps, a drastic departure from the average.

For instance $k = 5$ gives $n = 31$, and

$$31 \to 47 \to 71 \to 107 \to 161 \to 242$$

climbs to $242$ in five steps (indeed $3^5 - 1 = 242$). The rampage of $27$ in Example 3.2 has the same cause: the orbit of $27$ passes through $31$ along the way. Since we can manufacture as many “numbers whose orbits happen to have consecutive odd steps” as we like, we see here another reason why probabilistic arguments alone cannot prove the conjecture.

References

• J. C. Lagarias, “The 3x+1 problem and its generalizations”, American Mathematical Monthly 92 (1985), 3–23. — The standard introductory survey, covering the history and the main results.
• J. C. Lagarias (ed.), The Ultimate Challenge: The 3x+1 Problem, American Mathematical Society, 2010. — A collection including the survey above. The first place to look for the current state of the art.
• R. Terras, “A stopping time problem on the positive integers”, Acta Arithmetica 30 (1976), 241–252. — The original paper proving that the set of natural numbers with finite stopping time has density $1$.
• I. Krasikov and J. C. Lagarias, “Bounds for the 3x+1 problem using difference inequalities”, Acta Arithmetica 109 (2003). — A lower bound for the count of numbers up to $x$ that reach $1$.
• T. Tao, “Almost all orbits of the Collatz map attain almost bounded values”, arXiv:1909.03562 (2019). — The strongest result currently known, making the probabilistic intuition rigorous.
• D. Barina, “Convergence verification of the Collatz problem”, The Journal of Supercomputing 77 (2021). — Machine verification up to $2^{68}$.
• J. H. Conway, “Unpredictable iterations”, Proceedings of the 1972 Number Theory Conference, University of Colorado, 1972. — Undecidability of generalized Collatz maps.

Appendix: Hints for Doing It Yourself

A warning for your own experiments. The code in Section 3 is a naive implementation and becomes slow somewhere past $10^7$. The standard way to speed it up is memoization — storing the step count of each number already computed in a dictionary — as mentioned in the solution to Exercise 8.1. The dictionary grows huge, however, so it is more memory-efficient to stop as soon as the orbit falls below $n$ (that is, to compute only the stopping time $\sigma(n)$ and rely on Theorem 4.5).

Do not celebrate too soon. If you think you have found a counterexample, suspect integer overflow first. The 64-bit integers of C and Java overflow around $9.2 \times 10^{18}$. Just as $27$ climbed to $9232$, Collatz orbits rise many digits above their starting point, so testing numbers around $10^{18}$ will overflow along the way with ease. Python’s integers are automatically arbitrary-precision, so on this point you are safe.

For those who still want to try. As we have seen in this article, the naive probabilistic argument cannot exclude the $3n-1$ version (Proposition 7.1), and arguments by residue classes cannot get past the barrier of Remark 4.4. A new proof will have to capture the special role that the term $+1$ plays in the world of the positive integers. What that role is, nobody yet knows. On why mathematical problems become hard, see also Why mathematics is hard. For a contrasting example of a problem settled with heavy reliance on computation, see The four colour theorem (Theorem 5.1［The Four Color Theorem］), where the decisive point was the reduction to finitely many cases (unavoidable sets and reducible configurations（Definition 5.3）［The Four Color Theorem］). For the Collatz conjecture, no such means of finitization has yet been found.