This is a page about the Collatz conjecture. For those who don’t know the Collatz conjecture, a short explanation:
Think of a number larger than 1. Got it? Okay. Now, the rules are as follows:
- If the number you thought of is even, divide by two.
- If the number is odd, multiply by 3 and add 1.
Example: If you thought of 10, then you divided by 2, which gave you 5. However, if you thought of 5, you multiplied by 3 and added 1, which gave you 16.
The Collatz conjecture states that if you choose a number and keep repeating these two rules, you always end up with 1.
Example: If you started with 10, and you kept applying these two rules, you got the following sequence:
10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Now, the problem is that so far nobody has proved that the Collatz conjecture is true (it was proposed in 1937). Of course, you can try it out for a lot of numbers, up to a gazillion, but the problem with numbers is that there are always more to check. What you need is a proof the captures every possible number.
Messing around with the Collatz conjecture
Let’s state the Collatz rules more precisely:
- 2x -> x
- 2x + 1 -> 6x + 4
Even numbers are multiples of two. Odd numbers are an even number plus one. 6x + 4 is the result of multiplying by 3 and adding 1, like so: 3(2x+1)+1 = 6x + 3 + 1 = 6x + 4
Like I said before, I don’t have the mathematical skills for something like Collatz, so I just end up doing modular arithmetic. I do discover interesting stuff and I’d like to share it 🙂 If you see mistakes or if you have ideas, let me know! 😀
The below is a mix of mathematics and normal-language explanation.
Decreasing remainders (n – 1 mod n)
The first property I discovered is the following: Choose a number to which you want to apply the Collatz rules. Got it? Now, I’m giving you a number, say 4. Divide your number by 4 and write down the remainder. Now, apply the Collatz rules once to your number. Divide the result by 4 and write down the remainder. The discovery is this: If your first remainder was 3, then the second remainder is 2.
This holds for any number I give you. If I gave you 5 and you did the above, then if your first remainder was 4, the second remainder was 3.
In mathematical terms:
For every n >= 2, any number x such that x is congruent to n – 1 modulo n is mapped (x -> y) to a number y such that y is congruent to n – 2 modulo n
Restricting to even numbers
Another interesting bit is that you can cross out groups of numbers. For example, you can easily check that our rules above will bring any odd number to an even number in one step: If the number is odd, multiply by 3 and add 1. Multiplying two odd numbers (your number multiplied by 3) gives you another odd number. Adding one gives you an even number.
Basically what you have is that if the Collatz conjecture holds for all even numbers, it must hold for all odd numbers too, because an odd number is mapped to an even number and if the even number eventually reaches 1 then the odd number must too.
You can continue the above reasoning and I’ve gotten as far as showing that you can restrict your attention to numbers that
- are even, and
- if you divide by 3 you have a remainder of 1
In mathematical terms, you can restrict your attention to numbers x such that
x mod 2 = 0 and x mod 3 = 1
Interestingly, this also means that if I do this, I end up with a new set of rules:
- 24x + 4 -> 18x + 4
- 24x + 16 -> 6x + 4
- 12x + 10 -> 18x + 16
Under this new set of rules, it’s the number 4 we focus on: We need to prove that if we keep applying these rules, we will end up in 4.
How is this set of rules different from the first? It’s not that different. For example, the rules 24x + 16 -> 6x + 4 is a rule that does division by 4, which is dividing by 2 twice. The first and third rule are composed of both dividing by 2 and also multiplying by 3 and adding 1. So now we’ve got a new set of rules, how does that bring us closer?
I was hoping that continuing this (this restriction of numbers) indefinitely would go, in the limit, to a set of rules of the shape:
- ax + 4 -> cx + 4
- ax + b -> cx + d
with a > c and b > d …
Wishful thinking of course, but I wanted to write this stuff down if only to get it out of my head. I don’t want to be obsessed with this stupid conjecture anymore! >_< 😛