Start learning free

LESSON 134 OF 348 · LOOPS & CONDITIONALS

Collatz Conjecture in TypeScript: Printing the Series 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 / 1     => 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 while 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

    TYPESCRIPT · LOOPS & CONDITIONALS

    Collatz Conjecture in TypeScript, explained

    Problem overview

    The method printSeries receives a positive integer n and prints every value that n takes while the Collatz rules are applied to it. 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 Collatz conjecture says that, whatever positive integer you start with, repeating these rules eventually reaches 1. Nobody has proved this, but no counterexample has been found among the numbers that have been tried. The method prints the starting value, then each new value, and stops after printing 1.

    For n = 3 the sequence is 3, 10, 5, 16, 8, 4, 2, 1. Three is odd, so the next value is 3 * 3 + 1 = 10. Ten is even, so it becomes 5. Five is odd and becomes 16, which is halved three times (8, 4, 2) and then once more to 1. Each value is printed on its own line.

    Approach: repeat a transformation until a condition fails

    The example applies the same transformation over and over, and nobody knows in advance how many times. Some starting values reach 1 in a few steps, others take over a hundred. When the number of repetitions is not known up front, a while loop is the natural tool: it keeps going as long as a condition holds and checks the condition before every pass.

    The condition here is n > 1. The sequence is finished the moment n reaches 1, so as long as n is greater than 1, there is another step to take. Inside the loop, one decision is made each time: if n is even, halve it, otherwise triple it and add one. That is an if/else.

    Step by step

    1. Print the starting value first. The series begins with the input itself, and the loop only prints values it has just computed. If you skip this line, the 3 would be missing from the output for n = 3.
    2. Write the loop. while (n > 1) keeps running until the sequence reaches 1. The parameter n is an ordinary local variable inside the method, so the loop can update it directly. There is no need for a second variable.
    3. Handle the even case. An if checks n % 2 === 0, and inside it n becomes n / 2. In TypeScript, / gives a decimal result in general, but halving an even whole number always gives a whole number, so no rounding is needed.
    4. Handle the odd case. The else branch runs when the number is odd, and it sets n to 3 * n + 1.
    5. Print after the if/else. The console.log(n) sits inside the loop but after the whole if/else, so it runs once per pass for both kinds of step and shows the value that was just produced. Because the loop condition is checked afterwards, the last value printed is 1.

    The solution in TypeScript

    class Solution {
    printSeries(n: number): void {
        console.log(n);
        while (n > 1) {
            if (n % 2 === 0) {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
            console.log(n);
        }
    }
}

    Some TypeScript details about this code:

    • Parameters can be reassigned. n is a copy of the number the caller passed, since numbers are passed by value. Assigning to it changes only the local variable. If a caller holds a variable caller = 3 and passes it in, the variable is still 3 after the call.
    • Numbers are doubles. n / 2 is a true division and can produce a fraction, which is why the code only divides when the number is known to be even. Integers stay exact up to 2^53. The values in a Collatz series can climb well above the start: the series from 27 reaches 9232 before it falls to 1, and a very large start can pass the exact range.
    • The remainder test. n % 2 === 0 is true for even values. Using === compares numbers without any type conversion.
    • The annotation is erased. n: number helps the compiler, but at run time any value could be passed. A decimal start such as 2.5 is not covered by the conjecture.

    Why the loop ends

    That the loop always ends is exactly what the conjecture claims for positive integers. It is an open question in mathematics, but every start that has been tried does reach 1, and the series from 27 does so after 111 steps. That is why the code needs no counter or safety limit.

    Edge cases and common mistakes

    • Starting at 1. The first console.log prints 1, the loop condition is false straight away, and the output is just 1.
    • Forgetting the first print. The output would start with the second value of the series.
    • Printing inside only one branch. If console.log(n) is placed inside the if or the else, only one kind of step is shown. Putting it after both prints every value.
    • Printing before updating. A console.log(n) at the top of the loop prints the old value, so the series would end at 2 instead of 1 unless a print follows the loop.
    • Looping on n >= 1. At 1, the odd rule gives 4, and the series would cycle 4, 2, 1, 4, 2, 1 forever.
    • Zero or negative input. The task promises a positive integer. If you pass 0, the method prints 0 and stops, since 0 is not greater than 1. A negative number likewise prints once. The conjecture does not describe them.
    • Using a loop that counts. A for loop needs to know the number of steps in advance, and here the end is decided by the value itself.

    Testing

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