Take a number; if it is even, divide it by two (N’ = N/2), if it is odd, multiply it by three and then add one (N’ = N*3 + 1). Keep repeating these simple steps until you reach the result of N=1. This simple sequence is often called a “hailstone sequence” because the intermediate results sometimes go up, sometimes down, sort of like the path a small piece of ice follows inside a cloud, until it grows too large and falls down as hail.

If you start with N=1, you’re already at the end, so no further operations allowed. for N=2, you divide it by 2 and then you’re done, in one iteration. For number 3 it starts to get more interesting, as it takes a total of 7 iterations to complete the sequence:

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Number four is boring (4 -> 2 -> 1) and five is not much better (5 -> 16 -> 8 -> 4 -> 2 -> 1). We only get to do better than three above with six, which take one more iteration than three to complete:

6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Most numbers have fairly sort “runs”, while a few yield longer sequences. If we investigate the length of the next biggest sequence for ever increasing values of N, we see something like this for the first one thousand integers:

1: 0 2: 1 3: 7 6: 8 7: 16 9: 19 18: 20 25: 23 27: 111 54: 112 73: 115 97: 118 129: 121 171: 124 231: 127 313: 130 327: 143 649: 144 703: 170 871: 178

It gets progressively harder to beat these scores. Does every sequence always eventually collapse to one? Supposedly, yes, and this is known as the Collatz conjecture, after German mathematician Lothar Collatz. The hard part has been to formally prove the conjecture to be true. This problem is so infamous among mathematicians that I rather think the following xkcd is rather appropriate:

If you think about each number in the form of a node in a directed graph, then a particular node N for any number will have an outgoing edge towards N/2 (if N is even) or towards N*3+1 (if N is odd). As for edges incoming towards N, there’s ***always*** an edge from node N*2 towards N – that is because for any integer N, N*2 is always an even number, and thus will have an edge directed towards N. There may be an additional incoming edge towards node N if the result of (N-1)/3 is an integer odd number – for instance, if N=16, (N-1)/3 is 5, and thus there is an edge 5 -> 16 (because the next iteration for 5 is “times 3 plus 1”, and 5*3+1 = 16. This can be depicted as follows:

Generalizing the above, we can see that for the space of the positive integers, we can construct a graph where in the form N->N’ and every node will have a single outgoing edge. Because sometimes a node will have two incoming edges, some sequences will “merge” and follow a single path from that point forward. No sequence ever “splits” (that is, there is never more than one outgoing edge for each node), and so eventually all sequences merge in the final sequence 2->1

Plotting the graph for the first 1000 sequences, we can see some of the paths that emerge:

If we adjust the layout to better isolate the sequences, things look prettier:

Which can lead to some neat animations: (the image below is a rather large animated GIF, it may take a while to load and start “animating”)

Finally, while I was composing this post, I left my simple hailstone calculator running in order to see what would be the largest sequence it would find. As of this point, the largest sequence found by the program has 956 iterations, and it starts with number 226,588,897. The complete set of ever increasing “records” is the following:

1: 0 2: 1 3: 7 6: 8 7: 16 9: 19 18: 20 25: 23 27: 111 54: 112 73: 115 97: 118 129: 121 171: 124 231: 127 313: 130 327: 143 649: 144 703: 170 871: 178 1161: 181 2223: 182 2463: 208 2919: 216 3711: 237 6171: 261 10971: 267 13255: 275 17647: 278 23529: 281 26623: 307 34239: 310 35655: 323 52527: 339 77031: 350 106239: 353 142587: 374 156159: 382 216367: 385 230631: 442 410011: 448 511935: 469 626331: 508 837799: 524 1117065: 527 1501353: 530 1723519: 556 2298025: 559 3064033: 562 3542887: 583 3732423: 596 5649499: 612 6649279: 664 8400511: 685 11200681: 688 14934241: 691 15733191: 704 31466382: 705 36791535: 744 63728127: 949 127456254: 950 169941673: 953 226588897: 956