Felipe Tavares' Avatar

Someone is *WRONG* on the Internet!

Collatz conjecture fun

June 5, '23

Oh no, someone is *wrong* on the internet again!

I was quietly browsing Wikipedia the other day when I came across this small piece of code in the Termination analysis page:

void f(int n) {
   while (n > 1)
      if (n % 2 == 0)
          n = n / 2;
          n = 3 * n + 1;

Seems innocuous enough, right? It’s a little implementation1 of the Collatz conjecture.

The *issue* arises when I read the description:

As of 2021, it is still unknown whether this C-program terminates for every input

That can’t be right! How come such a simple program can’t be proven to terminate?! What a tragedy for computer scientists all around the world! Surely a 32 bit int is small enough to even brute force a solution here, no?

At first I thought “the problem space must be huge then, right?” but after a couple minutes thinking, it doesn’t seem to be the case - the state is a single int! This means there’s only about 4294967296 states to check!

Surely enough, we can write a little Rust program to check whether or not this dangerous little piece of seemingly logic-defying piece of C code does in fact terminates. The idea is simply to create a big vector with one entry per input state, initialize the state for 1 as we known the program terminates then and link all other states to the next until they eventually hit 1. Or in the case of this specific implementation, \( \le 1 \).

const MAX_C_INT: i32 = i32::MAX;

enum State {

fn main() {
    let mut graph: Vec<State> = vec![State::Terminates; MAX_C_INT as usize + 1];

    // Initialize the termination state for all numbers
    for n in 2..=MAX_C_INT {
        graph[n as usize] = if n % 2 == 0 {
            State::SameAs(n.wrapping_div(2).max(1) as usize)
        } else {
            State::SameAs(n.wrapping_mul(3).wrapping_add(1).max(1) as usize)

    // Follow the termination paths
    let mut unknown_termination: usize = 1;
    while unknown_termination > 0 {
        unknown_termination = 0;

        for n in 2..=MAX_C_INT {
            graph[n as usize] = match graph[n as usize] {
                State::Terminates => State::Terminates,
                State::SameAs(dst) => {
                    unknown_termination += 1;
                    graph[dst as usize].clone()

        println!("{}", unknown_termination);

And surely enough, consuming just a little bargain of 37GB of RAM, we have our answer:

❯ cargo run --release
    Finished release [optimized] target(s) in 0.00s
     Running `target/release/collatz-termination-rs`

Which means that we linked all states back to \(\le 1\) and our program does in fact terminate for every single possible input. So we can say that as of 2023, we know the program terminates2.

  1. However, it’s not a correct implementation. Notice that we use int to describe positive integers and use the > 1 check which on modular arithmetic (such as the one of ints) isn’t really saying the same as the conjecture. ↩︎

  2. Note this is a silly post about a silly mistake on Wikipedia. If you check other pages they will correctly mention this has been checked for even 64bits and larger. ↩︎