Project 1

CPSC 115L: Introduction to Computing

Fall 2010

Project 1: The 3n + 1 problem

CPSC 115-01: due Monday, October 18
CPSC 115-02: due Tuesday, October 19

For this project, you may work either on your own or with another partner of your choice from the same lecture section. If submitted as a pair, both you and your partner will receive the same grade.

Objectives

The main objectives of this assignment are

to give you practice designing and writing a simple Python program, and
to give you practice at using software to help solve an interesting problem.

Introduction

The 3n + 1 problem, also known as the Collatz conjecture, is an unsolved number-theory problem concerning a sequence of integers defined by the following process: Take any positive integer n. If n is even, then divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to the result to obtain 3n + 1. Repeat this process indefinitely. For example, if we start from n = 11, we have

11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

It is conjectured that, no matter what number you start with, you will always eventually reach 1.

1. The function `three_n_plus_1()`

1.1. Write an iterative function named three_n_plus_1 that takes a single integer parameter n > 0 and repeats the 3n + 1 process described above until n becomes 1. Your function should use a while loop to repeat the process. Implement your function in a file named three_n_plus_1.py.

1.2. Write a recursive function named three_n_plus_1_r that takes a single integer parameter n > 0 and repeats the 3n + 1 process until n becomes 1. Your function should use recursion to repeat the process. Implement your function in the file three_n_plus_1.py.

1.3. In the same file three_n_plus_1.py, test that your functions are correct by running them on different values of n and determining that they generate the same sequence in each case and that the sequence is correct. For each function, save snapshots of your tests for n = 1, 2, ..., 10 in a text file named three_n_plus_1.out.

2. Finding high water marks

As you experiment with your function, you will notice that some values of n take longer than others to converge to 1. That is, some values of n have longer stopping times than others. Consider a range of integers less than k. The starting value for n that has a longer stopping time than those of any other starting values less than k is called the high water mark for integers less than k. For example, the high water mark for integers less than 100 million is 63,728,127, with 949 steps.

2.1 Using either your recursive or iterative version of the function three_n_plus_1(), write a Python script, including whatever functions you need, to find the high water marks for the following ranges of integers:

n < 100
n < 1,000
n < 10,000
n < 100,000
n < 1,000,000

Note. Printing all the values of n during this computation will significantly slow down the run time of this experiment. Therefore, you may want to comment out your print statements for this part of the assignment. A good strategy might be to have your program print something like the following output during this experiment.

For n < 100, the high water mark is 97 with a stopping time of 118.

Implement your experiment in a Python script named collatz.py and save snapshots of your results in a text file named collatz.out. Make sure your functions are appropriately general, i.e., they make appropriate use of parameters.

Documentation

Each Python script should have a comment block at the beginning with your name, date, file name, and a brief description of the program, including the problem statement. Each function should include a docstring that describes the purpose of the function and its parameters.

What to hand in

Submit the following in paper:

For Part 1, printouts of the Python script three_n_plus_1.py and its output file three_n_plus_1.out.
For Part 2, printouts of the Python script collatz.py and its output file collatz.out.

Plagiarism and academic dishonesty

Please remember our course policy on plagiarism and academic dishonesty: You are encouraged to consult with one another when you work on homework assignments, but in the end everyone must do one's own work to hand in. In particular, discussion of homework assignments should be limited to brainstorming and verbally going through strategies, but it must not involve one student sharing written solutions with another student. In the end everyone must write up solutions independently. If you have discussed with classmates or used any outside source, you must clearly indicate so on your solutions and provide all references. Turning in another person's work under your name is plagiarism and qualifies as academic dishonesty. Academic dishonesty is a serious intellectual violation, and the consequences can be severe. For more details, read the Student Handbook 2010–2011, pp. 21–29.

CPSC 115L home page