\chapter{HAILSTONE WITH PARFOR}

\label{chapter_hailstone}


  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.75\textwidth]{chap_hailstone/collatz_sequence_27.png}
    \caption{Collatz sequence for 27}
  \end{centering}
  \end{figure}

  
\section{Introduction}

Pick a number.  If it's even, divide it by two, but if it's odd, triple it and add 1.
If you repeat the process, you get a sequence of numbers which seem to pop up and
plummet down unpredictably, the way a hailstone forms by repeatedly rising and falling
within a thundercloud.  For this reason, the numbers are sometimes called the
``hailstone sequence'', as well as the ``3n+1'' or ``Collatz sequence'', and they
have been a subject of interest to mathematicians and computational scientists for
years.

If we start with 7, for instance, we will compute the sequence
\begin{displaymath}
  7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, \ldots
\end{displaymath}
which begins to cycle when it reaches 1.  Although this process seems to reach 1 no
matter what starting point is used, this is still an open question known as the Collatz
conjecture.  We'll assume the sequence always terminates at 1.  For a given 
starting value $n$, then, two natural quantities of interest are $l(n)$, the length 
of the sequence, and $h(n)$, the ``height'' or maximum value, occurring in the sequence.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.80\textwidth]{chap_hailstone/collatz_count.png}
    \caption{Collatz  sequence lengths for 1 to 50}
  \end{centering}
  \end{figure}

\section{Computing the Length and Height}

It's remarkably hard to tell in advance whether the Collatz sequence of a number
will reach 1 quickly or not.  Thus, if we start with 27, we end up taking 111
steps before reaching 1, whereas starting at 26 and 28 take 11 and 19 steps
respectively.  It's easy to write a program that can compute $l(n)$ for any
value of n we choose:

\begin{lstlisting}
function l = collatz_length ( n )
%% collatz_length.m
%
  l = 1;
  while ( n ~= 1 )
    if ( n % 2 == 0 )
      n = n / 2;
    else
      n = 3 * n + 1;
    end
    l = l + 1;
  end
\end{lstlisting}

\begin{lstlisting}
function h = collatz_height ( n )
%% collatz_height.m
%
  h = n;
  while ( n ~= 1 )
    if ( n % 2 == 0 )
      n = n / 2;
    else
      n = 3 * n + 1;
    end
    h = max ( h, n );
  end
\end{lstlisting}

