#12
Collatz Sequence

The Collatz sequence, also called the 3n + 1 problem, is the simplest impossible math problem. (But don’t worry, the program itself is easy enough for beginners.) From a starting number, n, follow three rules to get the next number in the sequence:

If n is even, the next number n is n / 2.
If n is odd, the next number n is n * 3 + 1.
If n is 1, stop. Otherwise, repeat.

It is generally thought, but so far not mathematically proven, that every starting number eventually terminates at 1. More information about the Collatz sequence can be found at https://en.wikipedia.org/wiki/Collatz_conjecture.

The Program in Action

When you run collatz.py, the output will look like this:

Collatz Sequence, or, the 3n + 1 Problem
By Al Sweigart [email protected]

The Collatz sequence is a sequence of numbers produced from a starting
number n, following three rules:
--snip--
Enter a starting number (greater than 0) or QUIT:
> 26
26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Collatz Sequence, or, the 3n + 1 Problem
By Al Sweigart [email protected]
--snip--
Enter a starting number (greater than 0) or QUIT:
> 27
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

How It Works

The % mod operator can help you determine if a number is even or odd. Remember that this operator is a sort of “remainder” operator. While 23 divided by 7 is 3-remainder-2, 23 mod 7 is simply 2. Even numbers divided by 2 have no remainder, while odd numbers divided by 2 have a remainder of 1. When n is even, the condition in if n % 2 == 0: on line 33 evaluates to True. When n is odd, it evaluates to False.


 1. """Collatz Sequence, by Al Sweigart [email protected]
 2. Generates numbers for the Collatz sequence, given a starting number.
 3. More info at: https://en.wikipedia.org/wiki/Collatz_conjecture
 4. This code is available at https://nostarch.com/big-book-small-python-programming
 5. Tags: tiny, beginner, math"""
 6. 
 7. import sys, time
 8. 
 9. print('''Collatz Sequence, or, the 3n + 1 Problem
10. By Al Sweigart [email protected]
11. 
12. The Collatz sequence is a sequence of numbers produced from a starting
13. number n, following three rules:
14. 
15. 1) If n is even, the next number n is n / 2.
16. 2) If n is odd, the next number n is n * 3 + 1.
17. 3) If n is 1, stop. Otherwise, repeat.
18. 
19. It is generally thought, but so far not mathematically proven, that
20. every starting number eventually terminates at 1.
21. ''')
22. 
23. print('Enter a starting number (greater than 0) or QUIT:')
24. response = input('> ')
25. 
26. if not response.isdecimal() or response == '0':
27.     print('You must enter an integer greater than 0.')
28.     sys.exit()
29. 
30. n = int(response)
31. print(n, end='', flush=True)
32. while n != 1:
33.     if n % 2 == 0:  # If n is even...
34.         n = n // 2
35.     else:  # Otherwise, n is odd...
36.         n = 3 * n + 1
37. 
38.     print(', ' + str(n), end='', flush=True)
39.     time.sleep(0.1)
40. print()

Exploring the Program

Try to find the answers to the following questions. Experiment with some modifications to the code and rerun the program to see what effect the changes have.

How many numbers are in a Collatz sequence that begins with 32?
How many numbers are in a Collatz sequence that begins with 33?
Are the Collatz sequences for starting numbers that are powers of two (2, 4, 8, 16, 32, 64, 128, on so on) always composed of only even numbers (aside from the final 1)?
What happens when you enter 0 for the starting integer?