Math Forum Discussions

Guillermo Phillips

Posts: 37
Registered: 12/8/04

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

Plain Text

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 counter-example doesn't exist. I've
> encountered some odd stuff. For example, what I call a 6th Generation
> Quadracycle Pulsar with 4-bit Rep-unit and 2-bit 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 counter-example 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.