Comp 170 Lab 3: Collatz sequences

Comp 170 Lab 3 - Collatz sequences, Sept 24, 2007

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

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 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 (don't count the final "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), and have this return the length of the sequence.

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 a private field of the Collatz class for the max; this is what max_value is for. Alternatively, you can have collatzLen(N) return the length, and collatzMax(N) return the max value reached for the same sequence. (Note that collatz(N) can only return oneof len or max.)

Step 3: Reporting

Report the maximum length seen (and for what N), and also the largest max seen and for what N. If you get confused, work on just one of these at a time.

Suppose you're working on the maximum length. What you have to do is call collatz(N) for all N<=1000 (inside a loop, such as that in my range method). Start with two variables for the max length and the starting 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 max; note that you are looking for the maximum "max" value, that is, the "maxMax" and its position "maxMaxPos".

Email me your completed Collatz.java file, or a zipfile of the entire project.