The Rules of the Game
The Collatz Conjecture is a mathematical game with simple and easily understood rules. The point of the game is to show that every number, regardless of what is chosen, will decrease down to 1. It has been shown to be true up to insane levels, but has not been proven. That is to say, there is no written proof that shows that there can be no value that you start with that does not decrease to 1.
The rules are as follows:
- Pick a number.
- If the number is even, divide by 2.
- If the number is odd, multiply by 3 and add 1.
Initial observations on the rules
First, for any odd number, when you multiply by 3 and add one, you will always reach an even number. Odd times Odd is Odd, Odd plus Odd is Even.
Second, for any even number, when you divide by 2 as many times as you can, you will be left with an odd number.
Third, if you pick a number that leads to a lower number than you chose, then the number you chose can not be the lowest number that does not reach 1.
Thus, any number that decreases in value at all can be excluded as a potential failure.
The First Eliminations
For any value “x”, if x is even, then you can divide by 2, leading to a lower number, instantly eliminating all even values for x, leaving only odd values in the form 2k+1
2k+1 times 3 is 6k+3, plus 1 is 6k+4. This can be divided by 2 to reach 3k+2, which is higher than 2k+1… But if k is even here, then (3k+2)/2=(3/2)k+1, which is less than 2k+1
So, we can reorganize and say that if x=4k+1, then is decreases to 3k+1, and is lower than where we started.
Expanding out, we can therefore eliminate the following forms for x:
- x = 4k + 0
- x = 4k + 1
- x = 4k + 2
Leaving us only needing to check every 4th number, in the form x = 4k+3
The next steps are to recognize basic patterns that occur in the math, shapes that occur in the tree of these numbers, and to expand and eliminate further numbers.