Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!charon!lambert
From: lambert@cwi.nl (Lambert Meertens)
Newsgroups: comp.theory
Subject: Re: 3n+1
Message-ID: <2018@charon.cwi.nl>
Date: 27 Aug 90 18:44:37 GMT
References: <511@sun13.scri.fsu.edu>
Sender: news@cwi.nl
Reply-To: lambert@cwi.nl (Lambert Meertens)
Organization: CWI, Amsterdam
Lines: 32

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