ThatsMaths

Hailstones, in the process of formation, make repeated excursions up and down within a cumulonimbus cloud until finally they fall to the ground. We look at sequences of numbers that oscillate in a similarly erratic manner until they finally reach the value 1. They are called hailstone numbers.

The Collatz Conjecture

There are many simply-stated properties of the familiar counting numbers that appear certain to be true but that have never been proved. A prime example is Goldbach’s conjecture: every even number greater than 2 is the sum of two prime numbers.  In this category, we consider a conjecture made by Lothar Collatz, a German mathematician, in 1937. It is easily stated, but no one has ever proved it.

To explain the conjecture, we construct a sequence of numbers by a simple iterative process.  Let the first value be any positive whole number N. If N is even, divide it by two. If it is odd, multiply by 3 and add 1. Thus, we get a new number, either N/2 or 3N+1. The process is often abbreviated HOTPO, for “Half Or Triple Plus One”. We can represent this process in terms of a map:

Now we repeat the process over and over to generate a sequence. The Collatz Conjecture is that, no matter what value N we choose to start, the sequence always reaches 1 after a finite number of steps.

Let’s try a few examples: N=3 goes to 10, then 5, then 16, 8, 4, 2 and 1. After this it cycles forever between 4, 2 and 1, so we stop at the first occurrence of 1, giving a sequence of 8 numbers {3, 10, 5, 16, 8, 4, 2, 1}. Next, starting with N=7, we reach 1 after 17 steps {7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}.

So far it has been easy to compute the sequence mentally. But if we choose N=27 there are 112 numbers in the sequence, which reaches 9232 after 78 steps before finally descending to 1. The sequence, shown in Fig.1, is seen to oscillate wildly, illustrating the reason for the name hailstone numbers.

Fig. 1: Hailstone sequence for initial value N=27. The sequence reaches its maximum value of 9232 at step 78 and arrives at 1 in 112 steps.

The Collatz Conjecture has been checked for all starting values up to , and all cases end in the cycle {4,2,1}. Of course, this is not proof that the conjecture holds for all N, but it is powerful evidence. It is difficult to doubt that Collatz was right.

Fig. 2: Left: maximum value of the Collatz sequence as a function of N. Right: number of steps in the Collatz sequence as a function of N.

Generalizations of the Process

The HOTPO or 3N+1 process can be extended to negative integers, when it is found that every integer, positive or negative, eventually reaches one of five cycles. But this is another conjecture that has not been rigorously proved.

We can also iterate on real or complex numbers. Starting with a complex number z, the mapping

gives the next number. For integral z, this mapping reduces to the Collatz process

Iterating in the complex plane gives rise to the Collatz fractal, shown in Fig. 3. The main motivation for showing this result is that it is such a beautiful fractal image.

Fig. 3: The Collatz fractal, arising from the iterative map in the complex z-plane. [Source: Wikipedia article on the Collatz Conjecture. This image was selected as picture of the month on the Mathematics Portal for April 2007.]