Comp 170 Lab 3 - Collatz sequences, Feb 8

Goals

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
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.

For this lab, you are to test this for all N<= 1000. You are also to find the N in that range which gives you the longest sequence, and also find the N which gives you the largest sequence value. For N=7, the length of the sequence is 16 or 17 depending on whether you start counting at 0 or 1, and the largest value is 52.

Starter files are here.

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

    max = 250504 occurred at N=703
    longest sequence length = 178 occurred at N=871
Here is the output for the range N<= 10000: 
    max = 27114424 occurred at N=9663
    longest sequence length = 261 occurred at N=6171

Step 1: basic loop

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. Put the basic loop into a method, eg collatz(int N).

Step 2: max and length

Add checking for max and length, where max is the highest value of N reached and length is the number of iterations of the loop necessary to reach 1.

The loop method from Step 1 (I called it collatz(N)) can just set some private fields of the Collatz class, but I found it easier to have collatz(N) return a Stats object, which has max and len fields.

Step 3: Reporting

Report the largest max seen (and for what N), and also the longest len seen and for what N. This is trickier than it looks; do one at a time. Assume we're working on len:

What you have to do is call collatz(N) for all N<=1000 (inside a loop). Start with two variables for the max length and the starting N at which it occurred; I called them mlen and lenN. For each N you try, if len is the length of its sequence, check something like this: 

    if (len > mlen) {mlen = len; lenN = N; }
That is, save both the length and the value of N. At the end, print out mlen and lenN. Then do the same for max; note that you are looking for the maximum "max" value, that is, the "maxmax".

Email me your completed Collatz.java file.