Start with any positive integer x; if it is even, replace it by x/2, if odd by 3x+1, and repeat.

This problem is an old one (it goes back to at least the sixties), and
it has been referred to in many different ways: the 3x+1 problem, the
Collatz problem, the Syracuse problem, Kakutani's problem, Hasse's
algorithm, Ulam's problem.  Please, let us not call it Hofstadter's
problem also.

None of the essential questions have been solved.  It is not even known
if almost all positive integers end up going to 1.  A positive result is
that almost all positive integers have an iterate smaller than the
starting value.  The conjecture that all positive integers go to 1 has
been verified up to 2^40, and the length of a nontrivial cycle in
positive integers is at least 275,000.

Reference:
  The 3x+1 problem and its generalizations.
  Jeffrey C. Lagarias.
  The American Mathematical Monthly, Vol. 92, Nr. 1 (Jan. 1985),
  pp. 3-23.

[ Editor: the posting is unsigned and undated; the figures above are as
of its writing (Lagarias 1985 is the latest reference cited). ]

[ Editor: two later notes on the names and the literature of the
problem, from 1997 and 1998. ]

The problem which is given by Al DeSuda in its standard form is best
known as simply "the 3x+1 problem" but is also known as the Collatz
problem, the Syracuse problem, Kakutani's problem, Hasse's problem,
and Ulam's problem.  (Clifford Pickover has referred to it as the
Hailstone problem.)

I maintain a file on the problem (as well as files on quite a few
other problems).  The most recent paper I have is 1993, as of when it
was still unsolved.  It is difficult to believe it will be solved,
except by advanced mathematical techniques.

-- George Groth (npl-folk mailing list, May 1997)
   [ Editor: the message was sent from the address of Dana Richards
   <richards@cne.gmu.edu> but signed "george groth". ]

In article <fgrieu-1702981155190001@pppa119.francenet.fr>,
fgrieu@micronet.fr (Francois Grieu) wrote:
> Given a positive integer n, consider
>    a(0) = n
>  a(i+1) = a(i)/2         if a(i) is even
>  a(i+1) = (3*a(i)+1)/2   if a(i) is odd
> prove (or disprove) that for some i, a(i) = 1
>
> Has this problem (which my math teacher presented me as unsolved some
> 20 years ago) found a solution ?  who first coined it ?

Jeffrey Lagarias wrote a survey article on this problem for the
American Mathematical Monthly about 10 years ago.  It's available on
the web at
http://www.cecm.sfu.ca/organics/papers/lagarias/index.html

Lagarias says that it's also known as the Collatz problem, the
Syracuse problem, Kakutani's problem, Hasse's algorithm, and Ulam's
problem.  I am not competent to ascertain priority between these
claimants.

-- Robin Chapman <rjc@maths.ex.ac.uk> (February 1998)