ICS 4U – PROGRAM 05
COLLATZ CONJECTURE

INTRO TO THE COLLATZ SEQUENCE

A Collatz sequence is a sequence that starts with any positive integer n. If n is even, the next number in the sequence is n/2. If n is odd, the next number in the sequence is 3n + 1.

In the 1930s, mathematician Lothar Collatz conjectured that any sequence described above would eventually reach the number 1. It remains unproven to this day.

For example, let’s say we start the number 6. The Collatz sequence would be:

6, 3, 10, 5, 16, 8, 4, 2, 1

Let’s say we start with the number 9.

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

WORK

We will use our skills as programmers to study the world of math. This is an unproven mathematical claim. Perhaps it’s true, perhaps it’s false. So maybe there is a starting number that will never lead to 1.

a) Write a function collatz(int n) that gets an integer number as a parameter and returns a String containing the resulting sequence that ends with 1.

Example:
collatz(6) should return “6, 3, 10, 5, 16, 8, 4, 2, 1”

b) Try out your function from a) on starting numbers 1 through to 10 (using a for loop). Then try on numbers 1 to 100. Are all numbers you try ending with 1? (An infinite loop would suggest you found a number that doesn’t lead to 1.)

c) For some numbers, the sequence is quite long. Write a similar function collatzLength(int n) that gets an integer number as a parameter but instead returns the amount of numbers in the sequence until it finally reaches 1.

Example:
collatz(6) should return 9

d) Which number between 1 and 100 has the longest sequence? How many numbers does it have?

e) Try exploring with larger numbers. Can you see any patterns?

f) Write a program that checks all numbers between 1 and 100 000. Do not output the sequences, only output the number with the longest sequence.