The Shapes of Numbers

I am planning to re-start reading SICP, so I was looking around for some online course structure that I could follow. I found that UC Berkeley offers a course CS 61A titled SICP which uses Python as the language of instruction rather than Scheme. I was going through the course page and found a rather interesting homework problem

Q4. Douglas Hofstadter’s Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.

Pick a positive number n
If n is even, divide it by 2.
If n is odd, multipy it by 3 and add 1.
Continue this process until n is 1.
The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried – nobody has ever proved that the sequence will always terminate).

The sequence of values of n is often called a Hailstone sequence, because hailstones also travel up and down in the atmosphere before falling to earth. Write a function …

I have always been fascinated by the shapes generated by equations, so I wanted to ‘see’ this hailstone shape for myself. I wrote a little Ruby script to generate a hailstone sequence.

1
2
3
4
5
6
7
8
def hailstone(n)
  sequence = []
  until n == 1
    n = n.even? ? n/2 : n*3 + 1
    sequence << n
  end
  sequence
end

I generated the sequence for the first 100 numbers.

I then used the Grapher utility on the Mac to plot the resulting series. I found that the shape was like a sawtooth curve, oscillating up and down for a while before gracefully dying down to 1. This behavior was pronounced for odd and prime numbers more than even numbers (which tend to damp down quicker). Here’s a picture (click image to enlarge) of the hailstone series for 11, 59 and 89 (all odd and prime by choice):

Hailstone series

Further reading:
How are hailstone’s formed?
XKCD on Hofstadter

Comments