Puzzle: Snakes and Ladders

(also known as the Collatz conjecture, or Syracuse problem)


Courtesy of Calculator Fun and Games, which first introduced me to it, here's an interesting puzzle that is easy enough to understand, but which has developed into a far more complicated problem.  In fact, if you want to make the easy idea hard to understand, just go and read the Wikipedia entry - it is far too complicated, as much of maths on Wikipedia tends to be.


Anyway, here it is: Take a number - any number.  If it's odd, multiply by three and add one.  If it's even, divide by two.  Now take your new number and follow the same process - odd numbers multiply by three and add one, even numbers divide by two.  And so on, and so on.  

What do you find?  And, more importantly, does this always happen?


Let's try a few numbers:
35 is odd, so multiply by 3 ( = 105) and then add 1 = 106
106 is even, so divide by 2 = 53
53 is odd, so multiply by 3 (=159) and then add 1 = 160
160 is even, so divide by 2 = 80
80 is even, so divide by 2 = 40
40 is even, so divide by 2 = 20
20 is even, so divide by 2 = 10
10 is even, so divide by 2 = 5
5 is odd so multiply by 3 and add 1 = 16
16 is even, divide by 2 = 8, which is also even, divide by 2 = 4, then 2, then 1.


If (or should that be "When"?) you reach 1, then you stop.  Otherwise, you get stuck in a loop that goes 1 -- 4 -- 2 -- 1 -- 4 -- 2 etc.


The question is:  Do you always reach 1?  Is there a number out there somewhere that doesn't eventually drop down to 1?


The path length for numbers (how long it takes for a number to reach 1) is not predictable - certainly not easily, as far as I know, and so there's much research there as well.


For example, 26 follows the path 26 - 13 - 40 - 20 - 10 - 5 - 17 - 8 - 4 - 2 - 1


But 27 follows a completely different path...
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077,9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1


...with its highest point at over 9,000!  All in all, it has 111 steps in its path to 1.

Image from Calculator Fun and Games
(original was black and white line drawing)

Here are the paths for all the numbers 1-20 (and the numbers that they include):

Image from: "Professor Stewart's Hoard of Mathematical Treasures"

There are various puzzles connected with this problem.  The main one is to prove that all paths end at 1, but that's still not been completely solved yet, and some of mathematics' greatest minds are having a go.

A good alternative, though, is to find the longest path possible for three-digit and four-digit figures.  I'm not sure if it's a puzzle, or a game, and if it's a game, then I figure it'd probably spoil it for you to know the answer before you start :-)