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
Data Carrier Detect 