Start learning free

LESSON 134 OF 348 · LOOPS & CONDITIONALS

Collatz Conjecture in Kotlin: A while Loop with if and else

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

    KOTLIN · LOOPS & CONDITIONALS

    Collatz Conjecture in Kotlin, explained

    Problem overview

    The function printSeries receives an Int named n and prints every value that n takes in the Collatz sequence, one per line, starting with n itself and ending at 1. Each new term comes from the previous one by a simple rule:

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

    It is conjectured, though not proven, that every positive starting number eventually reaches 1. For n = 3 the output is 3, 10, 5, 16, 8, 4, 2, 1: 3 is odd, so it becomes 10; 10 is even, so it becomes 5; and so on until the sequence arrives at 1.

    Approach: repeat a transformation until a condition fails

    The number of steps isn't known in advance. It differs from one starting value to the next, so a loop that runs a fixed number of times doesn't fit. A while loop does: it repeats as long as its condition is true, and the condition here is "the current term is greater than 1".

    Inside the loop, an if and else choose between the two rules. Because exactly one rule applies to each term, the two branches are alternatives. After either branch the new term is printed, so the output has one line for the starting value and one for each step.

    Step by step

    1. Copy the parameter into a variable. Function parameters in Kotlin are read-only, so n can't be reassigned inside the function. Declare var num = n and update num instead.
    2. Print the starting value. The sequence begins with n, so it is printed before the loop.
    3. Write the loop with the condition num > 1. The sequence is finished when it reaches 1. The condition must test num, not n, because only num changes.
    4. Handle the even case. When num % 2 == 0, halve num. Integer division drops any remainder, but an even number has none, so the result is exact.
    5. Handle the odd case in the else branch: set num to 3 * num + 1.
    6. Print after the branches but still inside the loop. The statement then runs for both cases, once for every new term.

    The solution in Kotlin

    class Solution {
    fun printSeries(n: Int) {
        var num = n
        println(num)
        while (num > 1) {
            if (num % 2 == 0) {
                num /= 2
            } else {
                num = 3 * num + 1
            }
            println(num)
        }
    }
}

    The Kotlin details:

    • val versus var. A parameter behaves like a val: it can be read but not assigned. A local var can be reassigned, which is what the loop needs.
    • The type is inferred. var num = n gets the type Int from n.
    • num /= 2. This is shorthand for num = num / 2. Between two Int values, / is integer division, which truncates.
    • Return type. The function returns nothing useful, so it has the return type Unit, which Kotlin lets you leave out.

    Tracing n = 6

    The table shows the state at the top of each pass of the loop and the term printed by that pass.

    num at the loop testEven?New numPrinted
    6yes33
    3no1010
    10yes55
    5no1616
    16yes88
    8yes44
    4yes22
    2yes11
    1condition false, the loop ends

    The starting 6 was printed before the loop, so the full output is 6, 3, 10, 5, 16, 8, 4, 2, 1. Notice that the last printed value is always 1, and that the loop condition is checked again before every pass, never in the middle of one.

    Complexity

    The number of terms depends on the starting value in an irregular way. Numbers of similar size can give very different lengths: the sequence for 27 has 111 steps, while 32 needs only 5. No simple bound in terms of n is known, and whether every sequence ends at all is the open question the conjecture is about. The space used is O(1): a single variable, with output printed as it is produced.

    Edge cases and common mistakes

    • n = 1. The starting value is printed and the loop condition is false, so the output is just 1.
    • Powers of two. n = 8 only halves: 8, 4, 2, 1.
    • Printing in the wrong place. Putting the second println inside only one of the branches skips terms. Putting it before the if prints the old value twice and never prints the final 1.
    • Testing n in the loop condition. Since n never changes, the loop would not end for any start above 1.
    • Overflow. An Int holds values only up to 2,147,483,647, and the odd rule can make terms grow large. For n = 113383 a term overflows after 120 steps, wraps to the negative number -1812855948 and is printed. Because a negative number is not greater than 1, the loop then stops. Using Long for num avoids the problem, but the lesson's parameter is an Int.
    • Zero and negative inputs. The task doesn't expect them. They print the starting value and stop, because the loop condition is false.

    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 only 1.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free