Start learning free

LESSON 136 OF 410 · LOOPS & CONDITIONALS

Collatz Conjecture in Python: Print the Sequence with a While Loop

Practice Read the full explanation

The Collatz conjecture in mathematics asks whether repeating two simple arithmetic operations will eventually transform every positive integer into one. It concerns sequences of integers in which each term is obtained from the previous term as follows:
if the previous term is even, the next term is one half of the previous term.
If the previous term is odd, the next term is 3 times the previous term plus 1.
The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.

You are given an integer n and you should print to the console all the values that n takes throughout the Collatz Conjecture.

Example:

Input: n = 3

Output:
3
10
5
16
8
4
2
1

Explanation:
n = 3  => n is odd  => n becomes 3 * 3 + 1 = 10
n = 10 => n is even => n becomes 10 / 2    = 5
n = 5  => n is odd  => n becomes 5 * 3 + 1 = 16
n = 16 => n is even => n becomes 16 / 2    = 8
n = 8  => n is even => n becomes 8 / 2     = 4
n = 4  => n is even => n becomes 4 / 2     = 2
n = 2  => n is even => n becomes 2 / 2     => 1
n = 1 => stop
Hints:

Look at the example and notice that we apply a transformation over and over until we reach a final point where we stop. Does that ring a bell?

We need to repeat the transformation code as long as one condition holds (n is greater than 1). How do you write that in code?

We will use a loop that executes as long as n > 1. What should we do inside this loop?

If n is even, we should apply a transformation. Otherwise, we should apply the other transformation. How do we handle these different scenarios?

We can do this using an if - else statement.

Video Solution:

STEP 1 OF 5
    Ctrl + Enter to check

    PYTHON · LOOPS & CONDITIONALS

    Collatz Conjecture in Python, explained

    Problem overview

    The Collatz sequence starts from a positive integer n and repeats one rule until it reaches 1: if the current number is even, halve it; if it is odd, replace it with three times the number plus one. The Collatz conjecture says the sequence reaches 1 from every positive starting value. Nobody has proved it, but it has been checked by computer for enormous ranges, so the loop below does end for any value you are likely to try.

    The method printSeries(self, n) prints every value that n takes, one per line, starting with n itself and ending with 1. For n = 3 it prints 3, 10, 5, 16, 8, 4, 2, 1.

    Approach: loop while n is greater than 1

    The problem has the shape of a loop: apply the same update over and over until a stop condition holds. The stop condition is "n has reached 1", so the loop continues while n > 1. Inside the loop there are two cases, so it contains an if/else:

    • Even n (n % 2 == 0): the new value is n // 2.
    • Odd n: the new value is 3 * n + 1.

    Because the starting value must also be printed, and the loop prints each new value after computing it, the first print goes before the loop.

    Step by step

    1. Print n before the loop. The series begins with the input itself, and the loop only prints values it has just computed.
    2. Start a while n > 1 loop. Once n is 1 the sequence is over. Starting from 1, the loop body never runs, so only "1" is printed.
    3. Handle the even case. Test n % 2 == 0 and set n = n // 2. Use //: plain / returns a float in Python, so the printed values would look like 8.0 instead of 8.
    4. Handle the odd case in else. Set n = 3 * n + 1.
    5. Print n after the if/else, at the same indentation as the if, so it runs for both cases.

    The solution in Python

    class Solution:
    def printSeries(self, n: int):
        print(n)
        while n > 1:
            if n % 2 == 0:
                n = n // 2
            else:
                n = 3 * n + 1
            print(n)

    Python details worth knowing:

    • The parameter n is an ordinary local variable, so the loop may reassign it. The caller's own variable is not affected, because integers are immutable and the method only rebinds its local name.
    • Indentation defines the blocks. The last print(n) is inside the while but outside the if/else. Indenting it one level further would put it inside the else, so even values would never be printed.
    • Python integers have no size limit, so 3 * n + 1 cannot overflow, even if the sequence climbs far above the starting value. Starting from 27, for example, it reaches 9232 before it falls to 1.

    Complexity

    • Time: proportional to the length of the sequence, which is the number of loop iterations. There is no simple formula for this length in terms of n. It grows slowly: 27 takes 111 steps, which is far more than 3 takes (7 steps), though 27 is not much bigger.
    • Space: O(1). The method keeps only the current number.

    Edge cases and common mistakes

    • Starting at 1. The output is the single line 1.
    • Forgetting the first print. The output would then miss the starting value: for n = 3 it would begin with 10.
    • Printing before the update. If the loop printed first and then updated, the last value (1) would never be printed, or would need a separate print after the loop.
    • Using / for the even case. The values after the first halving turn into floats: for n = 3 the output would contain 5.0 instead of 5.
    • Writing while n != 1. The conjecture is about positive integers. With n = 0 a != 1 test loops forever, because 0 halves to 0, while while n > 1 stops at once on 0 and on negative numbers.

    Testing

    Calling Solution().printSeries(6) prints:

    6
3
10
5
16
8
4
2
1

    Starting from 6 halves to 3, and from there the sequence is the one for 3 above.

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free