The 3N + 1 Problem

My National Review Online "Diary" column for January 2004 included the following brainteaser.

The 3N + 1 Problem

—————————

T

Pick a positive integer N.  If it's even, divide by 2.  If it's odd, multiply by 3 and add 1.  Repeat until either you get tired or you reach 1.

Example:  9-28-14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1.

For any positive integer N, will this algorithm always reach 1 eventually?  Or will it loop somewhere?  Prove your answer.

———————————————
Uh-oh.  A reader sent this to me, and I did not know that it is actually an open conjecture — the Collatz Conjecture.  You can read all about it here.

If you did solve it, you can claim a $1,000 prize!