Hailstone number sequence

• If the number is odd, multiply by 3 and add 1
• Else the number is even; divide it by 2

The sequence is named for hailstones, since the process is much like the formation of a hailstone: start with a drop of water, which falls until it hits strong winds. These blow it back up, where a layer of ice is formed; then the stone starts falling down again. This process repeats itself in hailstones; do you know if all hailstones formed in this manner reach the ground? (Well, yes, because not every day is cloudy...)

Is it always the case that we reach 1? Nobody knows! The Collatz conjecture is that the process always reaches 1; it has been verified on computer for enormous numbers, and never been falsified. But this is not a proof, of course.

There are two ways in which the Collatz conjecture could fail:

• There exists some cycle other than the 4-2-1 cycle;
• There exists some number for which the hailstone sequence is unbounded, so we just encounter larger and larger numbers, but never repeat ourselves.

   Start  Num  Max Value   Break
--------------------------------
      27   96       9232      23
      31   91       9232      23
      47   88       9232      46
      63   88       9232      61
      71   83       9232      61
     703  132     250504     628
    1055  130     250504     628
    1407  132     250504    1256
    1583  127     250504    1256
    2111  130     250504    1256
    7279  125    1702276    3844
   10087  171    2484916    7688
   12399  122    2480056    8729
   13503  127    1052512   10696
   14695  130    2480056    8729
   15039  135    9635920   10049
   15131  127    2484916   11983
   22559  132    9635920   20098
   26623  106  106358020   26321
   31911   96  121012864   24928
   34239  150   18976192   32572
   35655  220   41163712   29405
   37503  205   35075104   21722
   41407  140    6454384   31123
   45055  181   13699096   43444
   45127  210   41163712   29405
   47867   94  121012864   24928
   50427  106  121012864   49856
   53247  106  106358020   52642
   53851   88  121012864   49856
   56095  119  106358020   52642
   56255  202   35075104   43444
   56731  101  121012864   49856
   57115  200   41163712   29405
   59903  101  106358020   52642
   60583   83  121012864   49856
   60975  207  593279152   52975
   64255  194   41163712   58810
   65307   96  521790496   51014
   67583  176   13699096   57925
   69535  171  593279152   52975
   73471   91  521790496   51014
   73755  132  139841152   65699
   75007  202   35075104   57925
   77031  145   21933016   65134
   77039  125   18976192   40667
   77671  Dno Dunno   1047216490

Num     Frq
------------
  1   38835
  3   19418
  6    4855
  8    4854
 11    1821
 13    2124
 16     909
 19     569
 21     803
 24     414
 26     558
 29     304
 32     226
 34     293
 37     163
 39     230
 42     121
 45     180
 47      89
 40      63
 52     103
 55      62
 57      87
 60      52
 63      35
 65      55
 68      32
 70      62
 73      31
 75      37
 78      21
 81      17
 83      22
 86      16
 88      23
 91      13
 94      15
 96      20
 99       8
101      11
104       9
106      15
109      14
112      10
114      12
117      10
119       9
122       4
125       3
127       6
130       4
132       4
135       2
140       1
143       1
145       1
150       2
163       1
171       2
176       1
181       1
194       1
200       1
202       2
205       1
207       1
210       1
220       1

The hailstone sequence can actually be calculated very quickly with some simple .x86 assembler. The input is put into eax, and ebx counts the number of cycles the number takes to reach 1.

xor ebx, ebx //Start the cycle counter at 0
mov ecx, 3   //Put 3 into ecx for multiplication
Parity:
cmp eax, 1   //Are we done yet?
je Done      //If so, go to the end
mov edx, eax //edx = eax
and edx, 1   //Get parity bit
cmp edx, 0   //Is it even?
je ParEven   //If so, skip straight to that part
//eax is odd here
mul ecx      //treble eax (ecx is just 3)
add eax, 1   //and +1
add ebx, 1   //increment cycle counter
//eax is now even, so flow straight into even handler
ParEven:
shr eax, 1   //divide by two
add ebx, 1   //increment cycle counter
jmp Parity   //time to test parity again
Done:

Just to clarify how this works:

• See if eax is 1 yet. If so, we're done.
• If not, get just the last bit of eax. Note that this determines whether eax is even or odd.
• If it is odd, triple and add one as usual.
• Now eax is certainly even - if it wasn't before, the previous step made it so.
• Half it quickly by shifting all the bits right. This is just like the quick method of dividing by ten in our usual base 10.
• Add one to the cycle counter, and start over.

There are a couple of micro-optimisations, which are allowed since the code is so simple. For example, we xor ecx against itself to set it to zero, rather than using mov. This is just showing off!

Please note this is MSAM. Strictly, we should use jr, in place of jmp with line lables. Likewise, the C-style comments would probably not be approved of but I thought it was more important that the code was understandable.