The Structure of Hailstone Sequences

Department of Mathematics




The Structure of Hailstone Sequences


(summary of the Original Written Report)

Exploratory Object Designer: Colin Phipps
Date: April 2004

Introduction

Every positive integer has a related Hailstone sequence defined in the following way: starting with a positive integer n, the next term in the sequence is 3n+1 if n is odd or n/2 if n is even. Repeating this process until you reach 1 yields the Hailstone sequence. Try a few numbers for yourself. You will notice that you will in fact reach 1, and that all of the sequences end in 16, 8, 4, 2, 1. The (unproven) Collatz conjecture states that every positive integer will eventually reach 1. The number of steps that it takes for the sequence to reach 1 is called the length of the sequence. I was immediately intrigued by the Hailstone Sequence and the Collatz conjecture because of the ease of comprehending the problem, the vast amount of evidence (it’s been computationally shown to hold up to 10x2^58) and yet the absence of a proof.  The leap that I took in this program was to imagine this sequence in reverse, a giant tree of positive integers that would all sprout from 1. In view of this, the Collatz conjecture could be verified by proving that all numbers appeared in this tree, called the Collatz graph.

Objectives

I wanted to develop a tool that would help me observe and perhaps understand patterns which would become evident while using this program to chart branches of the Collatz graph. Of course, all of this was done while keeping in mind a secondary goal of achieving theoretical results which could be used in an eventual proof of the conjecture.

I also wanted my program to make people look at the Hailstone sequence from a different point of view and to give them a sense of the larger picture.  I wanted to create a simple way of showing the overlying structure.

Results

I believe that patterns in this tree could lead to steps toward a proof of the Collatz conjecture.  There are many simple and more complicated patterns, if you consider these structures as your basic units of the graph (a couple are outlined as FACTS! in the program).  Realizing that the Hailstone sequence can be visualized in this way gives a simple reason as to why the amount of positive integers with a given length increases as the length increases.

Written by Colin Phipps, July 2007

Return to Student Learning Objects

Visit the Project