# 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;
else
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;

#[derive(Clone)]
enum State {
Terminates,
SameAs(usize),
}

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 {
}
}

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
2147483646
1550960379
1317017077
1136939144
762200279
128062193
565753
45
0


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. ↩︎