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 implementation^{1} of the Collatz conjecture.
The *issue* arises when I read the description:
As of 2021, it is still unknown whether this Cprogram 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 logicdefying 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 {
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/collatzterminationrs`
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 terminates^{2}.

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 ofint
s) isn’t really saying the same as the conjecture. ↩︎ 
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. ↩︎