Comp 170 Lab 3: Collatz sequences

Comp 170 Lab 3 - Collatz sequences

Goals

Indefinite while loops
Max revisited

Overview

Start with a number N. If N is odd, let the next number be 3*N+1. If N is even, let the next number be N/2. For example, starting with N=7, we have

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

The length of this particular sequence is 16 (we count steps in the process and so don't count the final "1"). We will also refer to the largest value encountered, 52 in this example, as the peak.

Many mathematicians have looked at this sequence, and this sequence as a result has been associated with all these names: Collatz, Kakutani, Thwaites, Hasse, Ulam. Because the numbers tend to move up and down for a while before reaching 1, just as hailstones move up and down in a cumulonimbus cloud before reaching the ground, this has also been called the "hailstone" sequence.

The basic conjecture is that, no matter what N you start with, you always eventually end up at 1. This has never been proven.

For this lab, you are to test this for all 1<=N<= 1000 and 1001<=N<=2000. You are also to find the N in each of these ranges which gives you the sequence with the maximum length, and also find the N which gives you the maximum peak value.

The starter zipfile is here.

Here is some output from my version, for the range N <= 1000:

    max peak value = 250504 occurred at N=703
    longest sequence length = 178 occurred at N=871

Here is the output for the range N<= 10000:

    max peak value = 27114424 occurred at N=9663
    longest sequence length = 261 occurred at N=6171

It is possible, for a single N, to find the length and the peak value in one loop, but it is tricky. So, although it is "wasteful" in some sense, I recommend separate functions of N to find length() and peak().

Step 1: basic loop; length() and peak()

Get the basic loop to work:

	while (N != 1) {
		if (N % 2 == 0) 	// Check if N is even!
			N = N/2;
		else
			N = 3*N+1;
	}

This should terminate for all N you try, but that doesn't exactly tell you much. It's found in the lab starter file as collatz(int N). Modify this to create collatz_length(int N), returning the sequence length, and collatz_peak(int N), returning the peak value.

Step 2: Ranges of N

Report the maximum length seen (and for what N), and also the largest peak seen and for what N. Your reporting method should take a given range of N; eg void range(int lowest, int highest). If you get confused working with length and peak simultaneously, work on just one of these at a time You can have separate methods rangeLen() and rangePeak() for the two cases, or you can have a single range() method handle the loop for length followed by a separate loop for peak, or (hardest?) you can have a single loop keep track of both.

Suppose you're working on the maximum length. What you have to do is call collatz_length(N) for all N in the range, eg 1<=N<=1000 (inside a loop, such as that in my range method). Start with two variables, for the max length and the N at which it occurred; I called them maxLen and maxLenPos. For each N you try, if len is the length of its sequence, check something like this:

    if (len > maxLen) {maxLen = len; maxLenPos = N; }

That is, save both the length and the value of N. At the end, print out maxLen and maxLenPos. Then do the same for peak; I used variables "maxPeak" and position "maxPeakPos".

Email me your completed project.