Credit: Eric Roberts
File: hailstone.py
Our world contains many interesting mathematical puzzles, many of which can be expressed in the form of computer programs. One such wonderful problem that is well within the scope of what we have learned is the hailstone problem.
The problem can be expressed as follows:
Pick some positive integer and call it n. If n is even, divide it by two. If n is odd, multiply it by three and add one. Continue this process until n is equal to one.
The following example, starting with the number 15, illustrates this process:
15 is odd, so I make 3n+1: 46
46 is even, so I take half: 23
23 is odd, so I make 3n+1: 70
70 is even, so I take half: 35
35 is odd, so I make 3n+1: 106
106 is even, so I take half: 53
53 is odd, so I make 3n+1: 160
160 is even, so I take half: 80
80 is even, so I take half: 40
40 is even, so I take half: 20
20 is even, so I take half: 10
10 is even, so I take half: 5
5 is odd, so I make 3n+1: 16
16 is even, so I take half: 8
8 is even, so I take half: 4
4 is even, so I take half: 2
2 is even, so I take half: 1
As you can see from this example, the numbers go up and down, but eventually, at least for all numbers that have ever been tried, comes down to end in 1. In some respects, this process is reminiscent of the formation of hailstones, which get carried upward by the winds over and over again before they finally descend to the ground. Because of this analogy, this sequence of numbers is usually called the Hailstone sequence, although it goes by many other names as well.
Write a program that reads in a number from the user and then displays the Hailstone sequence for that number, followed by a line showing the number of steps taken to reach 1. For example, your program should be able to produce a sample run that looks like this:
Enter a number: 17
17 is odd, so I make 3n + 1: 52
52 is even, so I take half: 26
26 is even, so I take half: 13
13 is odd, so I make 3n + 1: 40
40 is even, so I take half: 20
20 is even, so I take half: 10
10 is even, so I take half: 5
5 is odd, so I make 3n + 1: 16
16 is even, so I take half: 8
8 is even, so I take half: 4
4 is even, so I take half: 2
2 is even, so I take half: 1
The fascinating thing about this problem is that no one has yet been able to prove that it always stops. The number of steps in the process can certainly get very large. How many steps, for example, does your program take when n is 27?
Tip: when performing division with / in Python, the result will always be represented as a real number, even if the number is an integer. For hailstone, this means that calculated numbers may print out with a .0 at the end. To avoid this, try converting the divided value to be an int, like this: int(num / 2). Then you can print that value out, or store it into a variable, e.g. num = int(num / 2).
In order to solve the hailstone problem, we are going to need as way to determine if an integer is even or odd. In addition to the regular operators that you know and love (like +, -, *, and /) programming languages provide a remainder operator: %.
a % b
returns the value remaining when you divide a by b. For example, 10 % 3 is 1 because when you divide 10 by 3 you get 3 with 1 left over. When you divide any number by 2, the remainder is 0 if the number is even and 1 if the number is odd. Thus,
n % 2 == 0
is a test of whether n is even!