The Collatz conjecture is a nice little mathematical problem. Sounds very simple, but no-one can prove it, and it’s baffled many respectable mathematicians …
Basically you start with an integer, and follow two rules.
- if it's odd, triple it and add 1
- if it's even, halve it
Does it always reach 1 ?
Example
Start with 5.
- It's odd, so triple + 1 = 16.
- It's even, so halve it = 8.
- It's even, so halve it = 4.
- It's even, so halve it = 2.
- It's even, so halve it = 1.
Start with 7.
- It's odd, so triple + 1 = 22.
- It's even, so halve it = 11.
- It's odd, so triple + 1 = 34.
- It's even, so halve it = 17.
- It's odd, so triple + 1 = 52.
- It's even, so halve it = 26.
- It's even, so halve it = 13.
- It's odd, so triple + 1 = 40.
- It's even, so halve it = 20.
- It's even, so halve it = 10.
- It's even, so halve it = 5.
… and now we rejoin previous example from 5
- It's odd, so triple + 1 = 16.
- It's even, so halve it = 8.
- It's even, so halve it = 4.
- It's even, so halve it = 2.
- It's even, so halve it = 1.
You can then start building up maps of where the flow goes. This is all integers from 1 to 20, shaded by how many times they are visited.
So this one worked … but will all numbers get back to 1 ?
Proving it is hard. I wrote a tool to generate nice diagrams (as above) and search brute force … and gave up.