Start learning free

LESSON 143 OF 414 · LOOPS & CONDITIONALS

Collatz Conjecture in Rust: A while Loop That Prints the Series

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 6
    Ctrl + Enter to check

    RUST · LOOPS & CONDITIONALS

    Collatz Conjecture in Rust, explained

    Problem overview

    The function print_series takes an integer n and prints every value it takes while following the Collatz rules, one value per line, ending at 1. The rules are:

    • if the current number is even, the next number is half of it;
    • if the current number is odd, the next number is three times it plus one.

    The function does not return anything. Its result is the printed output. For n = 3 it prints 3, 10, 5, 16, 8, 4, 2 and 1. The conjecture says that every positive starting value eventually reaches 1. Nobody has proved it, but the function only has to follow the sequence until it arrives there.

    Approach

    The same transformation is applied again and again, and the number of repetitions is not known in advance. That is the signature of a while loop: keep going as long as a condition holds. Here the condition is that the current value is greater than 1.

    Inside the loop there are two cases, even and odd, so an if and else pick the right rule. After the number changes, the new value is printed. The starting value is printed once before the loop, because the series includes it.

    For n = 6 the function prints 6, then 3 (6 is even), then 10 (3 is odd), then 5, 16, 8, 4, 2 and 1. The loop stops when the value is 1, so 1 is printed as the last term and nothing follows it.

    Step by step

    1. Make a mutable copy of n. Function parameters in Rust are immutable, so num is declared with let mut and starts as n. The loop can then change num freely.
    2. Print the starting value. It is the first line of the output, and it must be printed even when the loop never runs.
    3. Open a while loop on num > 1. The test is on num, not on n. The loop changes num, so a condition on n would never change and the loop would never end.
    4. Handle the even case. When num % 2 == 0, divide it by 2. Division of two i32 values drops any remainder, but an even number divides exactly, so nothing is lost.
    5. Handle the odd case. In the else branch, set num to 3 * num + 1.
    6. Print after the if/else. The println! sits at the end of the loop body, outside both branches, so it runs once for every new value whichever rule produced it.

    The solution in Rust

    impl Solution {
    fn print_series(n: i32) {
        let mut num = n;
        println!("{}", num);
        while num > 1 {
            if num % 2 == 0 {
                num /= 2;
            } else {
                num = 3 * num + 1;
            }
            println!("{}", num);
        }
    }
}

    Some Rust details here:

    • println! is a macro. The ! marks it as one. The {} in the format string is replaced by the value that follows, and each call ends the line.
    • let mut. Bindings are immutable by default. Without mut, the line num /= 2; is a compile error, because it assigns to a binding that cannot change.
    • No parentheses around conditions. Rust writes while num > 1 and if num % 2 == 0 without them, but the braces are required.
    • The function returns (). With no -> in the signature and no final expression, it returns the empty tuple, which is Rust's "nothing". The lesson's tests look at what is printed.
    • Compound assignment. num /= 2 is shorthand for num = num / 2.

    Complexity

    The number of steps depends on how long the sequence is, not on a simple formula in n. For n = 27 the series takes 111 steps and reaches 9232 along the way, although 27 is a small number.

    Time: proportional to the length of the series, which is the number of loop iterations. Each iteration does constant work.

    Space: O(1). Only n and num are stored, and the values are printed instead of collected.

    Edge cases and common mistakes

    • n = 1. The function prints 1 and the loop is skipped, since 1 is not greater than 1.
    • Printing in the wrong place. If the println! sits inside only one branch, half of the values are missing. If the first print is left out, the output starts one term late.
    • Testing n instead of num. The loop would either run forever or not at all.
    • Zero and negative inputs. The sequence is defined for positive integers. For n = 0 or n = -3, the function prints the number once and stops, because the loop condition is false from the start.
    • Overflow. An i32 holds values up to 2,147,483,647, and the odd rule can push a series past that. The series for n = 113383 passes 2.4 billion. In an optimized build the value wraps to a negative number, the loop condition becomes false, and the printing stops early. In a debug build the same overflow panics. Ordinary test inputs stay far below this limit.
    • Using = in the condition. num % 2 = 0 does not compile. Comparison needs ==.

    Testing

    • n = 3 prints 3, 10, 5, 16, 8, 4, 2, 1.
    • n = 6 prints 6, 3, 10, 5, 16, 8, 4, 2, 1.
    • n = 1 prints just 1.
    • n = 2 prints 2, then 1.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free