Mathematical Background

In 1937, German mathematician Lothar Collatz made the following claim:

Take any number n. If it is even, divide it by two. If it is odd, multiply it by three and add one. Repeat this procedure with the result. No matter what value of n you start with, you will eventually end up with one.

This became known as the "Collatz conjecture" and, while no counterexample has ever been found, it has yet to be proven despite years of mathematical research. It remains an unsolved problem in mathematics.

In this assignment, you will implement code to allow the user to test this conjecture.

Part 1: collatz

In a file collatz.c fill in the following template:

#include <stdio.h>

int main(void)
{
/*
 * The main function should implement these steps:
 *
 * 1. Prompt the user to enter an integer n.
 *
 * 2. Check to make sure the integer is positive. If it isn't, print
 *    out an error message and exit.
 *
 * 3. Implement this pseudocode:
 *
 *       as long as n is not equal to 1,
 *           print the value of n on a line
 *           if n is even,
 *               divide it by 2 and store the result back in n
 *           otherwise,
 *               mulitply it by 3, add 1, and store the result back in n
 *       print the value of n on a line (it will be 1)
 */
    return 0;
}

Compile the program with:

$ cc -Wall collatz.c -o collatz

Here's an example your compiled program should duplicate:

$ ./collatz
enter n: 3
3
10
5
16
8
4
2
1

Part 2: collatz_count

As it stands, collatz only tests a single value of n. In this part, you'll build a program that tests it on a range of values from 1 to a user-provided maximum.

Create this program in a file collatz_count.c using this template:

#include <stdio.h>
#include <stdlib.h> // for exit()

int main(void)
{
/*
 * The main function should implement these steps:
 *
 * 1. Prompt the user to enter a(n integer) maximum n value maxN.
 *
 * 2. Check to make sure maxN is positive. If it isn't, print out an
 *    error message and exit.
 *
 * 3. Print a column header with "initial n" and "count" column names.
 *
 * 4. Implement this pseudocode:
 *
 *    for each value of initialN from 1 to maxN,
 *       set a counter to 0
 *       set n to initialN
 *       as long as n is not equal to 1,
 *           if n is even,
 *               divide it by 2 and store the result back in n
 *           otherwise,
 *               multiply it by 3, add 1, and store the result back in n
 *           increment the counter
 *       print the values of initialN and the counter
 */
    return 0;
}

(You may want to cut-and-paste from collatz.c to save typing.)

Note that you won't print out each n on each iteration of the loop, only the count of times the loop is run.

Compile the program with:

$ cc -Wall collatz_count.c -o collatz_count

Here's a typical run:

enter maximum n: 10
 initial n    count
         1        0
         2        1
         3        7
         4        2
         5        5
         6        8
         7       16
         8        3
         9       19
        10        6

You're welcome to try other initial n values for yourself. If you come across one whose Collatz sequence never reaches one, your program will loop indefinitely. If so, call the nearest mathematician immediately! B-)