# Exercise #39: Collatz Sequence

collatz(10)   [10, 5, 16, 8, 4, 2, 1] The Collatz Sequence also called the 3n + 1 problem, is a simple but mysterious numeric sequence that has remained unsolved by mathematicians. It has four rules:

·       Begin with a positive, nonzero integer called n.

·       If n is 1, the sequence terminates.

·       If n is even, the next value of n is n / 2.

·       If n is odd, the next value of n is 3n + 1.

For example, if the starting integer is 10, that number is even so the next number is 10 / 2, or 5. 5 is odd, so the next number is 3 × 5 + 1, or 16. 16 is even, so the next number is 8, which is even so the next number is 4, then 2, then 1. At 1, the sequence stops. The entire Collatz Sequence starting at 10 is: 10, 5, 16, 8, 4, 2, 1

Mathematicians have been unable to prove if every starting integer eventually terminates. This gives the Collatz Sequence the description of “the simplest impossible math problem.” However, in this exercise, all you need to do is calculate the sequence of numbers for a given starting integer.

Exercise Description

Write a function named `collatz()` with a `startingNumber` parameter. The function returns a list of integers of the Collatz sequence that `startingNumber` produces. The first integer in this list must be `startingNumber` and the last integer must be `1`.

Your function should check if `startingNumber` is an integer less than 1, and in that case, return an empty list.

These Python `assert` statements stop the program if their condition is `False`. Copy them to the bottom of your solution program. Your solution is correct if the following `assert` statements’ conditions are all True:

assert collatz(0) == []

assert collatz(10) == [10, 5, 16, 8, 4, 2, 1]

assert collatz(11) == [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

assert collatz(12) == [12, 6, 3, 10, 5, 16, 8, 4, 2, 1]

assert len(collatz(256)) == 9

assert len(collatz(257)) == 123

import random

random.seed(42)

for i in range(1000):

startingNum = random.randint(1, 10000)

seq = collatz(startingNum)

assert seq == startingNum # Make sure it includes the starting number.

assert seq[-1] == 1  # Make sure the last integer is 1.

Try to write a solution based on the information in this description. If you still have trouble solving this exercise, read the Solution Design and Special Cases and Gotchas sections for additional hints.

Prerequisite concepts: lists, `while` loops, modulo operator, integer division, `append()`

Solution Design

The function only needs a variable to keep track of the current number, which we can call `num`, and a variable to hold the sequence of values, which we can call `sequence`. At the start of the function, set `num` to the integer in `startingNumber` parameter and `sequence` to `[num]`. We can use a `while` loop that continues to loop as long as the `num` is not `1`. On each iteration of the loop, the next value for `num` is calculated based on whether num is currently odd or even. You can use the modulo 2 technique from Exercise #3, “Odd & Even” to determine this: if num % 2 evaluates to `0` then num is even and if it evaluates to `1` then `num` is odd. After this, append num to the end of the `sequence` list.

If `num` is exactly `1`, then the `while` loop stops looping and the function can return `sequence`.

Special Cases and Gotchas

The only special case is if the `startingNumber` parameter is less than 1, in which case there is no sequence and the function should return an empty list `[]`.

Now try to write a solution based on the information in the previous sections. If you still have trouble solving this exercise, read the Solution Template section for additional hints.

Solution Template

Try to first write a solution from scratch. But if you have difficulty, you can use the following partial program as a starting place. Copy the following code from https://invpy.com/collatzsequence-template.py and paste it into your code editor. Replace the underscores with code to make a working program:

def collatz(startingNumber):

# If the starting number is 0 or negative, return an empty list:

if ____ < 1:

return ____

# Create a list to hold the sequence, beginning with the starting number:

sequence = [____]

num = ____

# Keep looping until the current number is 1:

while num ____ 1:

# If odd, the next number is 3 times the current number plus 1:

if num % 2 == ____:

num = 3 * num + 1

# If even, the next number is half the current number:

else:

num = num // ____

# Record the number in the sequence list:

sequence.append(____)

# Return the sequence of numbers:

return ____

The complete solution for this exercise is given in Appendix A and https://invpy.com/collatzsequence.py. You can view each step of this program as it runs under a debugger at https://invpy.com/collatzsequence-debug/.