Collatz Conjecture Proof

The Collatz Conjecture:

Consider the following operation on an arbitrary positive integer:

•  If the number is even, divide it by two.
• If the number is odd, triple it and add one.

 Defined by the function f as follows:

For any positive starting integer, this process will eventually reach the number 1.

Direct Proof:

In binary, the following is equivalent to the Collatz process:

For any positive binary integer n, multiply n by three and add the least significant bit (LSB). Repeat until n reaches two to exponent x. I will refer to this as the LSB process.

Defined by the function f as follows:

Where n is our integer and b is the least significant bit (LSB).

Terminology:

Collatz process: The process defined by the Collatz Conjecture.

LSB process: The process described above under Direct Proof.

Base: The odd number that forms the starting point of a number.thread

Thread: A series of numbers where each consecutive number is equal to the base times 2x.

Table 1. Data for the example

Example:

Table 2. Collatz sequence, starting at 7

Table 3. LSB sequence, starting at 7

Table 4. LSB sequence, starting at 14

Collatz process compared to the LSB process:

Dividing by 2 shifts the binary number to the right until all of the zeroes on the right side of the binary number are eliminated, resulting in an odd number. This result is then used to calculate 3n +1 and find the next number thread. However, if we work in binary and use the LSB, we do not need to go through the process of dividing by 2 to find the next number thread.

Table 2 above shows the results of conducting the calculations for the Collatz process using 7 as our starting number. The calculated numbers are 11, 17, 13, and 5.

Table 3 above shows the result when we use the LSB process with 7 as our starting number. The results end up falling on to the same “thread” as the Collatz process. 22 is on the 11 thread. 68 is on the 17 thread. 208 is on the 13 thread. 640 is on the 5 thread.

Table 4 above shows the results if we use 14 (2 * 7) for our starting number. You can see that the results end up falling onto the same “threads” as the traditional Collatz calculations. 44 is on the 11 thread. 136 is on the 17 thread. 416 on the 13 thread. 640 on the 5 thread.

In all three cases illustrated in tables 2, 3, and 4, the calculated numbers land on the same threads, proving that the LSB process is equivalent to the Collatz process.

Adding the Least Significant Bit:

Table 5. Example results of 3n and 3n + 1 for the sequence beginning with 7

Table 5 gives a slightly more detailed view of the LSB process from table 3. Looking at the “3n+ 1 in Binary” column, you can see that when the LSB is added, the position of the LSB is shifted to the left, and the bits to the right of the LSB all end up set to zero.

Breaking it down to n + 2n + LSB:

When n is multiplied by 3, in binary, we are adding 2n to n. 2n is n shifted left by 1 bit. When the LSB is added to the result of n+ 2n, the LSB gets set to zero and 1 is carried over to the bit to its left. If that bit is 1, it will be set to zero and the bit will again be carried over to the left. As a result of this process, the lower bits will be wet to zero, and all of the 1 bits will gradually get set to zero, until the number contains just a single bit that is set to 1. This is illustrated in table 6.

Table 6. Breaking down 3n + LSB as n + 2n + LSB

Summary:

The LSB and Collatz process examples show how repeated calculations on a binary number will result in a binary number with just a single bit set to 1. They show how the LSB process is equivalent to the Colattz process. There have been millions of calculations done using the Collatz process, so there is nothing more that needs to be shown here using the LSB process that will add anything new. Since we are working in binary, once we show that a bit sequence terminates to just a single bit being set from carrying out the calculation, then any combination of those bit sequences will also terminate.

When you multiply a binary number by 3, you are adding the number shifted to the left by 1 with the original number. This is shown in table 6. So the number can only expand on the left by 2 bits at the most. When you add the LSB, the LSB is getting set to zero, 1 will carry over to the left, and adjacent bits to the left of the LSB that are 1 will also be set to zero. So on the right, at least 1 bit is set to 0, but  bits adjacent to the LSB that are 1 will also be set to zero. So with each calculation, it is likely more bits on the right of the number will be set to 1 than on the left. This will eventually result in a number with just a single bit set to 1.

Furthermore, any positive odd number, N, that is greater than 15 can be written as the sum of three odd numbers that have been proven using the function 3n + LSB. Therefore, the result of using the function on N will always produce a final result of 2 to some exponent.

Example:

27 = 11 + 9 + 7

So, since we can show that LSB process on 7 will result in 2 to some exponent, LSB process on 9 will result in 2 to some exponent, and the LSB process on 11 will result in 2 to some exponent, then the LSB process on 27 must also result in 2 to some exponent. Therefore, the LSB process applied to any positive odd integer must result in 2 to some exponent!

Conclusion:

The Collatz Conjecture is true.