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^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 Click here to return to the Mathematics Archives

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs