A Simplified Solution to the Collatz Conjecture (3x+1 problem)
I learned about the Collatz Conjecture today, which is one of the unsolved problems in mathematics. Tried to solve it and have an interesting proof which I believe solves it! Comments welcome.
Contact: collatz@tutanota.com
I am happy to present a more formal proof if there is any merit to this.
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Let’s use the binary representation for the “seed” numbers.
Lop-Off Rule:
Every number that is a power of 2 will fall to 1, i.e. numbers that can be represented as 2^n
You can assume that the “seed” numbers do not have any “0” bits on the right hand side (lowest bit) — because if they did then it is an even number and we keep dividing by 2 until the lowest bit is a 1 or we reach the end sequence (4, 2, 1). So it is safe to assume that each number we are dealing with always has a 1 as the lowest bit (i.e. by the “lop off rule”).
Calculation Format:
When computing 3x+1 we need to split that up as: x + (2x+1).
By doing this, we are assured that the “2x+1” number ends in a “11”. This is because doubling a number is equivalent to bit-shifting it to the left, so it ends in “0”. Then adding a 1 to it means it ends in “1”. Also, “x” (seed number) had to have ended in a “1” based on the lop-off rule, and so “2x+1” ends in a “11”.
Now let’s compute “x + (2x + 1)”. To do this, let’s represent all bits in “x” except the lowest bit with the letter “A”.
000A1
+ A11
— — —
(A+1)A0 => applying the “lop off rule” (divide by 2) and we get (A+1)A.
Add to 0 bit Rule:
Any two bits added to 0 will always result in either a value of “0”, “1”, or “10”, but never a “11”.
0 + 0 + 0 = 00
0 + 1 + 0 = 01
1 + 0 + 0 = 01
1 + 1 + 0 = 10
Calculation always ends in 0 Rule:
Since we always add “1” + “1” in the “x + (2x+1)” method then we always end up with “0” as the lowest bit, which we can lop off using the “lop-off rule”. This is equivalent to saying that 3x+1 always results in an even number.
Lowest 0 bit retained Rule:
When computing 3x+1 using the calculation format described above, the right-most 0 in “x” (seed) will always be added to a 1 from the “2x+1” (because the “2x+1” is bit shifted to the left so the bit on the right of the “0” is now being added to the “0” — and the bit on the right of the “0” is by definition a “1”). It is also always the case that there is a “carry” to be added because the previous two bits being added have to be a “1” + “1” since we are working with the right-most 0 bit. This carry makes the calculation equal to “1 (carry) + 0 + 1” = “10” (binary). Thus, the 0 position value from the seed number remains as a “0” and we have a carry.
No Increase in number of 1s Rule:
We hypothesize that when we perform the 3x+1 computation, the number of 1s in the binary representation of the result increases. To give examples of this nomenclature, the number 5 (“101”) has two 1s, whereas 7 (“111”) has three 1s.
The numbers that produce the most 1s is when 1 is added to 1 and 1 which is: 1+1+1 which gives us 11. This will allow us to show that we will increase the number of 1s. We are going to try and disprove the hypothesis, i.e. disprove that performing the 3x+1 calculation on an all-1s representation will increase the number of 1s in the binary representation of the end result.
Let’s see how this plays out with an example of all 1s: “1111111111” (10 bits of which 10 are 1s) because anything where we do not start off with all 1s will the same or less 1s based on the “Add to 0 Rule”.
001111111111+ (10 bits of which 10 are 1s)
011111111111 (11 bits; the 2x+1 addition from the calculation method described above)
— — — — — —
101111111110 (12 bits of which 10 are 1s).
Thus this disproves the hypothesis because this counterexample shows that when performing the 3x+1 calculation the number of 1s in the binary representation does not increase.
This also results in “10111111111” after applying the “lop-off-rule”.
Note that the above isn’t entirely accurate, here’s an example where it does increase (but reduces again one the second iteration):
0100011111111 + (12 bits of which 9 bits are 1s)
1000111111111
— — — — — — —
1101011111110 (13 bits) => 110101111111 (12 bits of which 10 bits are 1s)
But if we perform the calculation again:
00110101111111 + (12 bits of which 10 bits are 1s)
01101011111111
— — — — — — —
10100001111110 (14 digits) => 1010000111111 (13 digits of which 8 bits are 1s)
However, in the second iteration new find that it reduces. This is a result of having 1 consecutive 0 vs 3 consecutive 0s.
We can try the same thing with 2 consecutive 0s but we will end up with the same result, that there is no increase in the number of 1s when performing the “3x+1” calculation
Propagation of 0 Rule:
In the above calculation from the “No Increase in number of 1s Rule” we have seen that even when adding all 1s, we end up with a “0” that is right before the MSB. Note that anything where we do not start off with all 1s will the same or less 1s based on the “Add to 0 Rule”.
Let’s try computing 3x+1 with the result from the previous calculation so we can test what happens when there is a 0 present:
0010111111111 + (11 bits of which 10 bits are 1s)
0101111111111 (12 bits)
— — — — — — —
1000111111110 (13 bits) => 100011111111 (12 bits of which 9 bits are 1s)
0100011111111 + (12 bits of which 9 bits are 1s)
1000111111111
— — — — — — —
1101011111110 (13 bits) => 110101111111 (12 bits of which 10 bits are 1s)
As we can see, the 0 has “expand out and towards the right side” after multiplying by 3x+1 and dividing by 2. In particular, the first 1 on the right of the last 0 in the seed is getting converted to a 0 (after lopping off from the end result). i.e. the 9th from right @ 2⁸ got converted to a 0 above. Additionally there are extra 0s. This is the “Propagation of 0 Rule” which shows that with every subsequent 3x+1 calculation (and divide by 2), the 0 bit is expanding to the right.
Eventual Divide by 2 Drop-off:
Let’s try computing 3x+1 with the result from all but one 1 value at the end:
010000000001 + (11 bits of which 2 bits are 1s)
100000000011 (12 bits)
— — — — — —
110000000100 (12 bits) => 1100000001 (10 bits of which 3 bits are 1s)
The above shows that when there are a lot of 0 values (as a result of the propagation of 0 rule) we will see the number of bits reduce by 1 even though the number of bits that are 1 will increase by one. Since there are so many 0s, they will eventually all get lopped off too and we will keep increasing our density of 1 bits as a percent of total bits (but not total number of 1 bits). However, from our “No increase in the number of 1s rule” above we can see that even though we will be left with mostly just 1 bits, the number of 1 bits will not increase. Thus we will only increase the number of 0 values which will get lopped off and reduce the number of bits, until we are a power-of-2 value which will reach the end sequence of 4, 2, 1. This is the “eventual divide by 2 drop-off rule”.
The way we see this “eventual divide by 2 drop-off” rule as a pattern in practical patterns of various seed numbers is that most numbers have a sharp dropoff and end up in an odd number (like we did in our example above), until the 1 gets shifted to the left again and we have some more lop-offs further causing the number to get smaller. As the upswings happen, we are effectively just moving the 1 bit to the left and reducing the total number of bits in the number, until we eventually reach a point where we are at a power of 2 and end up in the end sequence of 4, 2, 1.
The above results in a proof that we will always end up with the 4, 2, 1 sequence for any positive number even extending up to infinity.
SOLVED
