Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Collatz Machine
Posted:
May 1, 2002 5:28 PM


Is the Collatz Conjecture still just a conjecture?
I have some ideas, please feel free to shoot me down if they sound dumb.
It strikes me that the Collatz Conjecture is well suited to representation in binary. This is due to the odd/even and divide by 2 nature of the conjecture:
a) if a number is even divide it by two b) if the number is odd then multiply by 3 and add 1.
Further, there seems to be three parts to the construction of the problem.
1. An even number is divided by two. 2. An odd number is multiplied by three. 3. Unity is added to a number.
I'll examine these three parts in what follows.
1. Firstly only even numbers are divided by two. That is numbers that end in a '0' in their binary representation strip of the final '0' as a result:
1010 > 101 100 > 10 111110 > 11111
and so on. Now numbers with any number of '0's will get reduced so that they always end in '1', by repeated use of rule (a) of the conjecture:
1010 > 101 1101000 > 1101 1000 > 1.
2. Any odd number multiplied by three will also be an odd number. Quite simply after multiplying by three the representation will always end in '1'
1 > 11 11 > 1001 101 > 1111
etc.
3. Adding 1 to an odd number will result in an even number.
My first line of attack is to examine the following iteration: a) If the number is odd add one to it. b) If the number is even then divide it by two.
What does this do to an initial starting number? Let me examine rule (a): How do you add 1 in binary? Starting from the right: if the position contains a '0' make it a '1'. If the position contains a '1' make it a '0' and carry a '1' to the left and repeat. The net effect is that consecutive '1's are flipped to '0' until a '0' is reached:
0111 > 1000 1010111 > 1011000 10001 > 10010
Rule (b) then kicks in to strip off any final '0's. The result of the complete iteration, is that any initial number will have its righthand '1's stripped off and its rightmost '0' flipped to a '1':
10111 > 11 10101 > 1011 10011  101
So the above iteration can be seen as a counter. How so? By reducing the number of '0's between each successive iteration by one each time until the final numbers reaches 1. Example:
10101 > 1011 > 11 > 1 10001 > 1001 > 101 > 11 > 1 101101 > 10111 > 11 > 1.
In general the number of iterations needed to reach 1 is the same as the number of '0's in the initial number plus 1. So the number 10101 has two '0's and takes three iterations.
This feature allows you to categorise any (odd) starting number, by the number of '0's contained between its starting and ending '1's. I'll call this the 'degree' of the number. What has this to do with Collatz? Well starting with an odd number and multiplying it by three will always allow you to add 1 to it and divide succesively by 2. These means that once Part2 has been applied then Part3 and Part1 can always be applied. This means that in order to follow the course of succesive iterations of the Collatz rules one needs to keep track of the number of '0's in the number. (x+1)/2 always reducing the degree by 1 and 3x potentially increasing the degree. So what does multiplying a number by 3 really do? And especially what does it do to the degree of a number?
Firstly multiplying by three doesn't care about how many '0's there are to the righthand side of the number, the bit pattern is kept intact:
1 > 11 10 > 110 100 > 1100
This suggests that multiplying by three can be modelled using a Finite State Machine and indeed it can. But firstly we modify the number fed into the FSM, so that it has an infinite number of '0's both to the right and to the left of the number. For example:
101 > ...0000010100000....
The FSM doesn't care of course about all these '0's. The degree of the number still holds, we just count the '0's between the starting and ending '1's.
Here's the FSM:
State A: Input 0  Output 0 go to State A Input 1  Output 1 go to State B. State B: Input 0  Output 1 go to State A. Input 1  Output 0 go to State C. State C: Input 0  Output 0 go to State D. Input 1  Output 1 go to State C. State D: Input 0  Output 1 go to State A. Input 1  Output 0 go to State C.
The FSM reads succesive digits from right to left and begins in State A. You can verify this really does multiply by 3. Examining the machine a number of conclusions can be drawn.
1. The machine begins in State A and always ends in a loop in State A (by reading the infinity of '0's to the left of the number). 2. There are 5 primary loops defined by the following succession of States:
State A: Loops when inputting sucessive '0's (Loop A) State A  State B: Loops when inputing '1' followed by '0' successively. (Loop B) State C: Loops when inputting succesive '1's. (Loop C) State C  State D: Loops when inputing '0' followed by '1' succesively. (Loop D) State A  State B  State C  State D: Loops until the whole number is read. (Loop E)
Note that each of these Loops has a characterstic input and a charactersitic output. So how do these loops affect the Degree of the number being fed in?
Loop A: Outputs '0' so doesn't affect the Degree. Loop B: Outputs '11' reducing the number of '0's and therefore the degree by one each time around the loop. Loop C: Outputs '1' so doesn't affect the Degree. Loop D: Outputs '00' increading the number of '0's and therefore the degree by one each time around the loop.
The final step is to create an (Collatz) FSM that performs the mapping 3x+1 on a number with an infinite number of '0's either side of it. The divide by two rule then becomes irrelevant as the FSM gives the same bit pattern regardless of the number of '0's to the right.
And that's as far as my musings go. In order to solve the collatz conjecture I think you have to show that in general the 3x mapping increases the Degree by less than one on average. A possible answer is to stack an infinite number of Collatz FSMs together and verify that any number input, will always result in a singular '1' output with an infinity of '0's either side of it. To be honest I haven't got a clue how to do that.
Thanks for your patience.



