The Collatz conjecture is an unsolved problem on whether following the following procedural will always to 1 for every positive integer.
Pick any positive integer:
- If it’s even, divide it by 2.
- If it’s odd, multiply it by 3 and add 1.
- repeat
Formally, we can define a recurrence relation in modular arithmetic notation:
For example, start with 12, we have 12 ➜ 6 ➜ 3 ➜ 10 ➜ 5 ➜ 16 ➜ 8 ➜ 4 ➜ 2 ➜ 1