CIT 591 Assignment 2: Collatz's Problem Fall 2005, David Matuszek

# Purposes of this assignment

• To get you started programming in Java
• To familiarize you with:
• Pair programming
• Variable declarations
• Simple output
• `if` statements, `while` loops, and assignment statements

This is a lot to learn for a first assignment.

# Overview

Consider the following algorithm, defined for positive integers:

• Choose a number.
• As long as the number is not 1, do the following:
• If the number is even, cut it in half.
• If the number is odd, multiply it by 3 and add 1.

Example: If you start with the number 17, you get the following sequence:

• 17 -- this is odd, so multiply by 3 and add 1, getting 52
• 52 -- this is even, so divide by 2, getting 26
• 26 -- this is even, so divide by 2, getting 13
• 13 -- this is odd, so multiply by 3 and add 1
• 40 -- this is even, so divide by 2, getting 20
• 20 -- this is even, so divide by 2, getting 10
• 10 -- this is even, so divide by 2, getting 5
•  5 -- this is odd, so multiply by 3 and add 1, getting 16
• 16 -- this is even, so divide by 2, getting 8
•  8 -- this is even, so divide by 2, getting 4
•  4 -- this is even, so divide by 2, getting 2
•  2 -- this is even, so divide by 2, getting 1
•  1 -- stop

Does this process always terminate at one, or is there some starting number that will cause it to spiral out of control, either going into a loop or repeatedly getting larger and larger? This is called Collatz's problem, or sometimes Ulam's problem or Scott's problem (the origin isn't entirely clear). It is known that, for the first few billion integers, the process always terminates at one.

The sequences generated in this way contain some fascinating patterns. If this is the sort of problem that appeals to you, the computer is a great way to help discover some of these patterns.

## Part one

Write an application that does the following:

1. Prints out your name and the name of your partner, followed by a blank line. (Even if the assignment doesn't require it, it's always a good idea to put your names someplace visible in the output or screen display.)
2. For each of the numbers 1 through 99, print out a line that begins with the number, then the sequence of numbers that results from starting with the given number, ending with the `1`. Separate the numbers by spaces. For example, starting from the number 17, you would print the single line:
`17 52 26 13 40 20 10 5 16 8 4 2 1`
3. Insert an extra space before each single-digit number (a number less than 10). This will make your output neater.

## Part two

When you have part one working, add code to it to do the following.

1. Keep track of which starting number gives the longest sequence, and how long that sequence is. Do this within the loops that compute the sequences. Count both the starting and the ending number. (For example, the starting number 17 gives a sequence of length 13.)
2. At the end of the program, print an English sentence containing these two numbers (the starting number that gave the longest sequence, and the length of the sequence). Don't just print the bare numbers without any words to tell what they are.

## Notes:

You are expected to work as closely as possible with your partner. Please exchange email addresses so that you can communicate after lab is over. Try to follow the pair programming methodology as carefully as you can.

 What is pair programming? Two programmers working side-by-side, collaborating on the same design, algorithm, code or test. One programmer, the driver, has control of the keyboard/mouse and actively implements the program. The other programmer, the observer, continuously observes the work of the driver to identify tactical (syntactic, spelling, etc.) defects and also thinks strategically about the direction of the work. On demand, the two programmers can brainstorm any challenging problem. Because the two programmers periodically switch roles, they work together as equals to develop software. -- Laurie Williams North Carolina State University Computer Science

This is a fairly easy assignment, so some of you may finish before the end of the lab period. Future assignments will get progressively longer and more challenging.

Unless I specify otherwise, you are welcome to use any Java that both you and your partner know in doing the assignments.If you know some bit of Java you would like to use, and your partner doesn't, the best approach is to have your partner write that part, under your guidance. Both of you are expected to understand the program completely.

Turn in only one copy of the assignment, via Blackboard. Zip up the entire BlueJ project, which should be a folder that contains the `.java` and `.class` files, along with a couple of other files created by BlueJ for its own use. You and your partner should decide which of you is going to turn in the assignment (since I want only one copy of it), but both of you should be satisfied with it before you turn it in. Whoever turns it in, use Blackboard's note feature to indicate who your partner is.