The Collatz Conjecture is an allegedly-unsolved problem in mathematics.

I say allegedly there because, reading those words, I feel like mathematicians are going to jump out from my closet yelling, “You got punk’d!” for being duped into believing it’s unsolved.

The Collatz Conjecture

The Collatz conjecture concerns a Sequence of positive integers with the following rules:

1. If the current term is odd (congruent to 1 (mod 2)), the next sequence will be 3n+1.
2. If the current term is even (congruent to 0 (mod 2)), the next sequence will be n/2.

The conjecture is that all positive integers will eventually converge to 1. In this blog post, I will prove this conjecture.

Preliminaries

Any positive integer can be represented as the sum of positive powers of 2. This basically means you can encode any positive integer in binary.

Multiplying by 3 is the same as left-shifting the binary string by 1, then adding the original Number.

3 * n == (n 

Dividing by 2 is the same as right-shifting the binary string by 1.

n / 2 == (n >> 1)

By modelling integers as binary strings, the proof becomes much easier to visualize.

Analysis

When you apply the 3n+1 rule, you’re shifting the existing number to the left by 1, adding the original number, then adding 1.

If the lowest bit of the current item in the sequence is 1, the next item in the sequence will always have the lowest bit cleared; a.k.a. congruent to 0 (mod 2). This occurs with a probability of 1. Getting n/2 next is the inevitable consequence of any odd item.

If the lowest bit is 0, the next item in the sequence has an even 50% probability of being 0 or 1. This means you have a 50% chance of shrinking the next item (progressing closer to 1) or growing it. However, the growth will always be followed by a 100% chance of shrinking.

Thus, your decision flow looks like this:

• Odd -> P(1) Even (progress towards 1)
• Even ->
  • P(0.5) Odd (grow next item) -> P(1) Even
  • P(0.5) Even (progress towards 1) -> …

You always have at least one (n/2) after each odd item in the sequence.

You can have an infinite length of halvings without reaching another (3n+1) step–but once you do, the immediate next step is guaranteed to be (n/2).

Informally Proving the Conjecture

Any two steps of the Collatz sequence will result in the following three possible outcomes:

• Odd, Even (P = 0.50) -> (3n + 1)/2
• Even, Odd (P = 0.25) -> (3n + 1)/2
• Even, Even (P = 0.25) -> (n/4)

(Odd, Odd) is not possible. Once you get an odd, the next step is always Even.

The number of evens that follow an odd is always at least 1. The number of odds that follow an even is at most 1.

The sequence will bias for at least as many even outcomes than odd. The degenerate case is that the number of odds and evens is equal. Therefore, we should focus only on the worst case.

Since these are the only two outcomes possible for any two-step window of the sequence, the proportion of two transformations is sufficient to decide convergence.

Theorem: If the ratio of G:S is less than 1, the sequences converges.

We calculate the coefficient of Growth (G) for two steps as the derivative of (3n + 1)/2, which yields 3/2.

We calculate the coefficient of Shrinkage (S) for two steps as the derivative of (1/(1/4)), which yields 4.

Since there are at least as many shrinkage events as growth events, and S > G, (3n + 1)/2 will always grow an integer by less than (n/4) would shrink it.

Therefore, this sequence will always converge. And it converges to 1 for all positive integers.

What If You Change the Parameters?

If you remove the +1 from (3n+1), odd numbers will diverge (towards infinity) and even numbers will converge to 1. This is because the sign is preserved across steps. This is also true of even coefficients with the +1 preserved.

If you change the coefficient 3 from (3n+1) to a larger integer k, such that G >= S, this sequence will sometimes diverge and sometimes converge to 1. This may be undecidable for some values of k (e.g. 7).

If you change the coefficient to an even number and remove the +1, you will create a cycle that never converges for even numbers.

If you change the halving step, all of my above analysis goes out the window.

It is only because the growth step is (3n+1) for odd values, and the shrink step is n/2 for even values, that the sequence will always converge to 1.

On the Probability Distribution of Bits

It’s irrelevant to this analysis.

The worst case for convergence is to cycle between odds and evens throughout the lifetime of the sequence. Odds can only yield an even in the next iteration. Successive evens only accelerate convergence.

The only thing that matters is how the two-step window behaves and the coefficients G and S.