In articles which discuss the hailstone problem, you will often find comments to the effect that some numbers should continually increase rather than eventually decrease to 1, based on the fact that odd numbers are multiplied by 3, but even numbers are divided only by 2. Viewing the problem in that way is simplistic and misleading. It is better to break the Signature up into units which I will refer to as Signature Segments, where a segment is defined as any portion of a Signature which begins with O and continues with all of the letters up to but not including the next O. Signature Segments figure prominently in the discussion relating to The Hailstone Tree 

Without fail, all segments begin with OE, which implies:-

  • Multiplication by 3.
  • Addition of 1.
  • Division by 2.
Following the division by 2, our number may be odd or even with equal probability.

This implies that:-
It will terminate at OE or extend beyond OE, with equal probability of 1/2.

If it extends beyond OE
It will terminate at OEE or extend beyond OEE, with equal probability of 1/4.

If it extends beyond OEE
It will terminate at OEEE or extend beyond OEEE, with equal probability of 1/8.

Ans so on...

Clearly, the probability decreases by a factor of 2 for each E added to the segment, so longer segments are progressively less likely. However they do have a greater impact on the hailstone process due to the greater number of divisions by 2.

The reasoning presented above is captured in tabular form in the following:-.

 Signature Segments  [D]ivisions by 2  [P]robability  [D]x[P]       [D]x[P] (normalised)
 OE   1  1 / 2     1 / 2  32768 / 65536
 OEE   2  1 / 4     2 / 4  32768 / 65536
 OEEE   3  1 / 8     3 / 8  24576 / 65536
 OEEEE   4  1 / 16     4 / 16  16384 / 65536
 OEEEEE   5  1 / 32     5 / 32  10240 / 65536
 OEEEEEE   6  1 / 64     6 / 64    6144 / 65536
 OEEEEEEE   7  1 / 128     7 / 128    3584 / 65536
 OEEEEEEEE   8  1 / 256     8 / 256    2048 / 65536
 OEEEEEEEEE   9  1 / 512     9 / 512    1152 / 65536
 OEEEEEEEEEE   10 1 / 1024   10 / 1024      640 / 65536
 OEEEEEEEEEEE   11 1 / 2048   11 / 2048      352 / 65536
 OEEEEEEEEEEEE   12 1 / 4096   12 / 4096      192 / 65536
 OEEEEEEEEEEEEE   13 1 / 8192   13 / 8192      104 / 65536
 OEEEEEEEEEEEEEE   14 1 / 16384  14 / 16384       56 / 65536
 OEEEEEEEEEEEEEEE   15 1 / 32768  15 / 32768       30 / 65536
 OEEEEEEEEEEEEEEEE   16 1 / 65536  16 / 65536        16 / 65536

Regarding the contents of this table.
  • Signature Segments.
    A list of possible Signature Segments which contain varying numbers of Es from 1 up to 16. Segments longer than this will of course be encountered when very large numbers are submitted to the hailstone process. Numbers having thousands of digits will be met and processed in later sections of this tutorial.

  • Divisions by 2.
    This is simply the number of Es contained within the segment.

  • Probability.
    The probability of a random Signature Segment being of this type. As discussed previously, each segment type has a probability of half that of the previous segment type. The sum of the probabilities in this column will approach a value of 1 as the list is extended.

  • [D]x[P].
    The product of the number of divisions by 2 and the probability of this segment being generated. The resulting number provides a measure of the overall likelihood of achieving a division by 2 by means of this segment when a segment is generated.

  • [D]x[P] (normalized)
    The numbers in this column have exactly the same values as the numbers in the previous column, but they have been normalized so that each number has a denominator of 65536. When we see a number such as 6144 / 65536, it tells us that when 65536 segments of a Signature are generated, 6144 of the divisions by 2 will be generated by segments which have the form OEEEEEE.

Adding all of the items in column 5 gives us the sum:-
131054 / 65536 which equals 1.9997. This is the average number of divisions by 2 generated by each Signature Segment. The fact that this number is so close to 2 is significant. In fact, adding additional lines to the table would move it even close to 2. Summing up then, each Signature Segment provides one multiplication by 3 (and an addition of 1) as well as an average of two divisions by 2. Reducing this thought to the simplest possible form implies that on average, calculating one additional Signature Segment for the number multiplies that number by a factor of 3/4.

A very interesting circumstance arises when we calculate a series of 8 consecutive Signature Segments. On each of the eight occasions the subject number will be multiplied by a factor which, in the long run, will average out at 3/4. What actually happens is encapsulated in the following mathematical statement.

38 / 48 = .10011

In short it gives us a division by a number very close to 10. This in turn translates to a reduction in the size of the number being processed of one digit. To a first approximation then, an n digit number will generate n*8 Signature Segments on its journey to the expected concluding value of 1. This is the basis for what I call The Rule of 8 which you will meet later in this tutorial. I believe you will be pleasantly surprised at how closely numbers right across the vast number spectrum obey this rule when you get to the subject matter considered at Introduction to the Hailstone Program and at The Hailstone Rule-of-8 Demonstration 

Three important caveats.

This Rule of 8 is only an approximation (although a remarkably stable one), and as a result small departures from it will be caused by the following:-

  • The 3 in the mathematical statement is always accompanied by the addition of 1. This is not expected to cause a big departure in the operation of the Rule, but it is always present, and the departure is always in the same direction.

  • The 4 is the average calculated in the Signature Segment analysis shown above. On any given Segment calculation it will in fact be some power of 2, but averaged over a large number of calculations the probabilities involved will dictate that the outcome will be a division by very close to 4.

  • The mathematical statement above doesn't give us exactly one tenth, although it is a remarkably accurate approximation. As a result, we are entitled to be quietly confident that the Rule of 8 will be closely observed.