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



Re: Collatz Machine
Posted:
May 2, 2002 4:57 PM


Thanks for your perusal.
> >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. > > If I understand you correctly, then you are wrong. The number 10101010101010101 > is degree 8 but becomes 100000000000000000 after one iteration of 3x+1. So > doesn't this degree 8 number become a degree 0 number after one iteration?
The degree is relevent as it allows you to get a grip on how far down the tree the number is towards '1'. I think was trying to point out that the 3x portion of the conjecture is the most important part to concentrate on and a good way to get a handle on what it does to the number is to count the number of zeroes. In fact your example is great at showing how 3x affects the number of zeros. Each '10' is converted into '11' (with reference to the FSM) This means that the number of zeroes decrease by the same number of '10' repetitions. This means that your number '10101010101010101' is very close to the bottom of the tree.
> > Well, I think the FSM may be too much trouble. I do my binary math using perl > (which has arbitrary lenght strings). You can "multiply by 2" by appending a > "0" onto the right end of an arbitrary length string of binary digits. In fact > you can save a step by appending a "1" then adding to the original. And doing > binary addition with strings is easy. I also normalize the two operands to the > same length to account for the carry. Thus, to perform the 3x+1 operation on > 10101010101010101: > > > 0010101010101010101 original number, normalized by appending "00" to left end > 0101010101010101011 shift left (with increment), normalized with "0" at left > 1000000000000000000 sum > > And I like removing all the least signifigant 0s in one step, which is easy > with perl's regular expression interpreter. >
I particularly like the simplicity of the FSM and the way it simplifies the whole problem to one of following state transitions. These state transitions give you a lot more information than purely binary numbers and allow you to watch the development of a series of numbers. Also the state transitions are fixed by the originating number and indeed define the whole sequence of numbers. Your completely right to point out that this is just a cellular automaton, but I think it's a very predictable one and can be done for an infinite number of steps. Collatz iterations behave rather like a crystal growing on a substrate, it takes on the shape of the surface it grows on initially, but after a while becomes regular and ordered and eventually 'forgets' the initial topography. This can only mean that information about the initial number is lost with each successive Collatz iteration  I thought that one way of quantifying that information loss is to count the number of zeroes. That may be a bit simplistic but it's a start.
> > > >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. > > Well, I think the infinite quantity of FSMs may be problematic. > > And I am not convinced yet that a counterexample doesn't exist. I've > encountered some odd stuff. For example, what I call a 6th Generation > Quadracycle Pulsar with 4bit Repunit and 2bit Resonator requires 4098 bits > to construct. Alas, this is a dead end since Pulsars converge, but it is > reminiscent of cellulat automata. I think a counterexample may be some kind of > self regenerating pattern that could require millions of bits. And since the > Collatz Distiributed Computing Project is only up to the 50 bit range, I don't > think they'll ever notice a Pulsar let alone anything more complicated such as > the 6th Generation Type 2.1.2.1.1 Mersenne Hailstones, the first of which has > over 53,000 decimal digits and requires over 800,000 iterations to reach 1.
A million bits is just 1.2 Megabytes not much in today's money. In fact that is the only thing to prove, is that no cycles exist other than the one involving '1'.
Here's my FSM for a complete Collatz iteration. Note the starting number is cushioned in an infinite number of zeroes and the machine starts in State S. The number 'drifts' to the left, but all I care about it ending up with the number '1'. Have fun, I do:
S: in 0 out 0 state S. in 1 out 0 state A. A: in 0 out 0 state B. in 1 out 1 state A. B: in 0 out 1 state C. in 1 out 0 state A. C: in 0 out 0 state C. in 1 out 1 state D. D: in 0 out 1 state C. in 1 out 0 state A.
Thanks.



