mayne@VSSERV.SCRI.FSU.EDU (William (Bill) Mayne) (08/27/90)
I have seen references in a few popular books (Poundstone's "The Recursive Universe" and Hofstadler's (sp?) "Godel, Escher, Bach" come to mind.) to a problem known variously as "Ulam's problem" or "the 3n+1 problem." Simply stated it is this: Take any positive integer n. If n is even divide by two, otherwise take 3*n+1. Calculations have shown that by repeating this process every number up to a trillion eventually leads to 1. Then sequence then enters the cycle 1, 4, 2, 1... The interesting thing is that some take a long time to reach 1, first growing to much larger values and then shrinking back and so forth in ways which seem unpredictable by simple inspection. The problem is to prove that every number leads to one. The name "Ulam's problem" stems from the fact that Stanislav Ulam worked with it on early computers. A few years ago I and some others kicked this around by email. One guy had a proof I didn't really understand which, supported by calculations he did on a PC over several days supposedly proved there were no cycles of length less than some limit like 40,000, counting odd numbers only. I had an algorithm which would find any cycle of length below any chosen limit, if one existed, but running it for a length into the thousands would be unreasonable and besides wouldn't accomplish anything. The reason we amateurs looked at the question of the existence of cycles not containing 1 was that that would be the only kind of counterexample which could be demonstrated by calculation, and looking at the difficulties in that might give us some insight. We weren't naive enough to think we'd find any! The only published references I have found have just mentioned this as an unsolved problem and given few series of numbers. I haveqbeen unable to find anything in the literature about proof technigues which have been tried or any partial results, etc. Has anything other than a sketch of the problem been published? Have any partial proofs (such as that there are no cycles other than 1) been devised?
lambert@cwi.nl (Lambert Meertens) (08/28/90)
In article <511@sun13.scri.fsu.edu> mayne@VSSERV.SCRI.FSU.EDU (William (Bill) Mayne) writes: ) I have seen references in a few popular books (Poundstone's "The ) Recursive Universe" and Hofstadler's (sp?) "Godel, Escher, Bach" ) come to mind.) to a problem known variously as "Ulam's problem" ) or "the 3n+1 problem." [...] ) ) One guy had a proof I didn't really understand which, supported by ) calculations he did on a PC over several days supposedly proved there ) were no cycles of length less than some limit like 40,000, counting ) odd numbers only. [...] ) ) I haveqbeen unable to find anything in the literature about proof ) technigues which have been tried or any partial results, etc. Crandall [1] has proved that there are no non-trivial cycles of length 17,985, using the fact that all numbers < 10^9 eventually go to 1. Plugging the result (established by Yoneda) that this is so for numbers < 2^40 into Crandall's formula, Lagarias [2] found a lower bound of 275,000 on the length of cycles. That is the latest I heard. Reference [2] is a good overview of what is known about this problem. [1] R.E. Crandall, On the "3x+1" problem. Mathematics of Computation, 32 (Oct. 1978) 144, pp 1281-1292. [2] J.C. Lagarias, The 3x+1 problem and its generalizations. The American Mathematical Monthly, 92 (Jan. 1985) 1, pp 3-23. -- --Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl
martin@cs.umn.edu (Johnny Martin) (08/28/90)
<prob. description stuff deleted> > >The only published references I have found have just mentioned this >as an unsolved problem and given few series of numbers. >I haveqbeen unable to find anything in the literature about proof >technigues which have been tried or any partial results, etc. >Has anything other than a sketch of the problem been published? >Have any partial proofs (such as that there are no cycles other than >1) been devised? The following paper contains a reasonably good survey of the problem. Jeffrey C. Lagarias The 3x + 1 Problem and its Generalizations American Mathematical Monthly pp 3-23 January 1985 -- Johnny Martin (martin@umn-cs.cs.umn.edu) Dept. Comp. Sci., 4-192 EE/CS, University of Minnesota, Minneapolis MN 55455 --