Ask A Scientist Mathematics Archive

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!
------------------------------------------------
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^n-1, 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 write-up 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
=========================================================