UMBC CS 201, Spring 07
Spring '07

CSEE | 201 | 201 S'07 | lectures | news | help

CMSC 201
Programming Project Four

Hailstone Sequences

Out: Monday 4/16/07
Due Date: Sunday 4/29/07, before midnight

The design document
for this project, design4.txt, is due:
Before Midnight, Sunday 4/22/07

The Objective

The purpose of this assignment is to give you practice with recursion, strings and chars, allocating memory dynamically, and writing to files.

Consider the following problem:

Choose a positive integer and repeatedly do the following: if the number is 1, quit; if the number is even, cut it in half; and if the number is odd, multiply it by 3 and add 1. For example, if you start with the number 17, you get the sequence:
17   52   26   13    40   20   10    5   16   8    4   2   1.
Generate the sequence from a starting number and you'll find the numbers go up and down like a hailstone in a cloud before it plummets to earth (e.g., when the value is one).


Does this procedure eventually reach 1 and stop for every choice of starting number? So far, this is an unsolved problem -- no one has yet proved that the process always results in 1, and no one has yet found a counterexample. This problem was first posed by L. Collatz in 1937 and goes under several names: the Collatz conjecture, the '3n+1 conjecture', the Ulam conjecture, and the Syracuse problem. The sequence is also commonly called the hailstone sequence.

John Conway proved that the original Collatz problem has no nontrivial cycles of length less than 400. Lagarias (1985) showed that there are no nontrivial cycles with length less than 275,000. Conway (1972) also proved that Collatz-type problems can be formally undecidable. The conjecture has been check by computer for all start values up to 1.2 × 10**12, but a proof of the conjecture has not been found. Paul Erdös said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 for its solution. There are some heuristic, statistical arguments supporting the conjecture: if one considers only the odd numbers in the sequence generated by the Collatz process, then one can argue that on average the next odd number should be about 3/4 of the previous one, which suggests that they eventually hit the bottom.

The Task


  • We guarantee that the graders will enter only integers as their response to prompts for values and only single characters as their response for the menu choice.

    Sample Run

    Here is a link to the sample output of this program.

    Submitting the Program

    To submit your program, type the following command at the Unix prompt

    submit cs201 Proj4 followed by the .c and .h files necessary for compilation

    To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

    submitls cs201 Proj4

    CSEE | 201 | 201 S'07 | lectures | news | resources | help | Tuesday, 17-Apr-2007 15:49:09 EDT