

The famous 3X+1 problem Algorithms
Name: Unknown
Status: N/A
Age: N/A
Location: N/A
Country: N/A
Date: Around 1993
Question:
Here is a tough one: prove that the following iterated algorithm
converges for all positive integers: n(i+1) = { n(i)/2 if n is even, {
(3*n(i)+1)/2 if n is odd. This is known as the #3X+1 problem, the Collatz
Conjecture, or a host of other names. Various cash prizes have been offered
for its solution. If you generalize and parameterize the algorithm, I suspect
that the 3X+1 algorithm lies on the boundary of sets of algorithms that
converge. The trouble is: I have no idea if that set is open or closed!
Replies:
I am afraid I do not understand what you mean by converge. It
certainly cannot converge to a single n(i), because the only fixed points are
0 and 1, which are not accessible to positive integers. Do you perhaps mean
converges to some periodic cycle, rather than diverging to infinity? A simple
test tells me everything seems to converge to the cycle 1 2 1 2 1 2...Is that
correct? So, who gets the cash if somebody here solves it? Maybe it is a
good way to raise money for Newton, though...A few ideas from my thoughts on
the problem so far: (1) Numbers of the form 2^n  1 produce the longest
strings of increasing values (3*n+1)/2 all odd. For example, try 2047. (2) If
the sequence produced has roughly half odd and half even numbers, then it must
converge, because for odd numbers the values are multiplied by 3/2 (roughly)
while for even numbers they are divided by 2, so the even's decrease sequence
values more than the odd's increase sequence. (3) It is of course easy to
prove the conjecture holds for integers up to any value you like, just by
explicitly forming the sequences. Each sequence actually tells you about the
convergence of every integer that is obtained in that sequence, because of
course they all follow the same path. So there should be special numbers
(including the 2^n1, perhaps?) that produce the longest sequences. Can these
be characterized in some way? In particular can we show that eventually the
number of odds and evens must balance? Of course I would like to hear what
else has been done on this. I do not think I have ever seen anything
published on it, but then this is not the sort of thing I do my work in.
There were fair number of articles published in math journals during the 80's
on this problem...search on 3X+1 or Collatz. So, it turns out there is a big
long writeup in the American Mathematical Monthly, vol. 92, p. 3 (1985). And
Paul Erdos is quoted as saying that Mathematics is not ready for this problem.
Don't you think maybe you could have mentioned this in introducing it here?
Before the rest of us make fools of ourselves, I mean... Sometimes it is
better if you do not know the history of a problem. After all, didn't Fermat
write in his diary that he had an "elegant solution proof" of his Last
Theorem, and mathematicians have been working on it ever since, and the
recently announced proof is far from elegant!
Arthur Smith
Click here to return to the Mathematics Archives
 
Update: June 2012

