(close)

Use this link to get 70% off the Automate the Boring Stuff online video course.

Support me on Patreon

Prev: Clickbait Headline Generator | Next: Conway's Game of Life
Use this link to get 70% off the Automate the Boring Stuff online video course.

Support me on Patreon

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.

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

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()
```

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?