The 3*n*+1 conjecture, due to Collatz, is that any positive
integer, *n*, iteratively operated upon by two simple rules leads
to 1, having visited a possibly lengthy series of integers. The rules
are that *n*, if odd, is converted to 3*n*+1, and, if even, is
divided by 2. Each new *n* is treated by the same rules,
repeatedly, until 1 is reached. The conjecture remains unproven. Its
mathematical proof is the challenge.

A review on the Internet (and in *The 3x+1 problem*, Amer.
Math. Month1y (1985), 3-23) of the status of work on this conjecture by
Jeffrey C. Lagarias stated that the problem currently *appears*
intractable. The Internet pages are at
http://www.cecm.sfu.ca/organics/papers/lagarias/index.html .
There is also a book: Gunther J. Wirsching, "The Dynamical System Generated
by the 3n+1 Function" Lecture Notes in Mathematics (Springer Verlag, 1999), 1681
An article in
Wikipedia is devoted to the Collatz conjecture.

The reader is referred to these for references, a more elegant presentation of the iterative function, a variety of equivalent statements of the problem, and much mathematical detail.

Since 27 is often cited as the example of a small integer which illustrates how tortuous the trajectory to 1 can be, I'll list the sequence of odd integers encountered in that trajectory.

27 - 41 - 31 - 47 - 71 - 107 - 161 - 121 - 91 - 137 - 103 - 155 - 233 - 175 - 263 - 395 - 593 - 445 - 167 - 251 - 377 - 283 - 425 - 319 - 479 - 719 - 1079 - 1619 - 2429 - 911 - 1367 - 2051 - 3077 - 577 - 433 - 325 - 61 - 23 - 35 - 53 - 5 - 1

In a little more detail, in case you missed it, that arises from:

27*3+1 gives 82; 82/2 gives 41 then

41*3+1 gives 124; 124/2/2 gives 31 then

31*3+1 gives 94; 94/2 gives 47 then ...

(omitting a number of steps in which only one or two divisions by 2
are required)

445*3+1 gives 1336; 1336/2/2/2 gives 167

(which is the first instance in
this trajectory where more than 2 divisions by 2 are required)

...

Even from the vantage point of the structure to be presented here, which accommodates these tortuous vagaries, it is not hard to see how confounding a problem it is.

My Collatz Home Page Index to Terms Used