3n+1 Problem Statement

The 3n+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 3n+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