Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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.
|
|
|
|
