Start learning free

LESSON 136 OF 410 · LOOPS & CONDITIONALS

Collatz Conjecture in Java: Printing 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

    JAVA · LOOPS & CONDITIONALS

    Collatz Conjecture in Java, explained

    Problem overview

    The Collatz sequence starts from any positive integer and repeats one rule. If the current number is even, halve it. If it is odd, multiply it by 3 and add 1. The conjecture says that every positive starting number eventually reaches 1. Nobody has proved it, but it has been checked by computer for an enormous range of starting values.

    The method printSeries receives an int named n and prints every value that n takes, one per line, starting with n itself and stopping when the value reaches 1. For n = 3 the output is 3, 10, 5, 16, 8, 4, 2, 1. The method prints and returns nothing, which is why its return type is void.

    Approach: repeat a step until a condition fails

    You do not know in advance how many steps the sequence needs. For n = 6 it takes 8 steps, and for n = 27 it takes 111. A for loop with a fixed count does not fit this problem, but a while loop does, since it runs as long as a condition holds and the number of repeats is not known up front.

    The loop condition is n > 1: the sequence ends when 1 is reached. Inside the loop there are two cases, even and odd, which is a natural if and else. Each pass computes the next term and prints it.

    The first value, n itself, has to be printed before the loop, since the loop only prints the values it produces. That also makes the case n = 1 work: the loop body never runs, and the output is the single line 1.

    Here is the sequence for n = 6, written the way the loop sees it:

    6
3
10
5
16
8
4
2
1

    6 is even, so it becomes 3. 3 is odd, so it becomes 3 * 3 + 1 = 10. From there 10 gives 5, 5 gives 16, and then halving takes 16 down through 8, 4 and 2 to 1.

    Step by step

    1. Print n with System.out.println before the loop. The sequence includes its starting value.
    2. Write a while loop that runs while n > 1. The parameter n is an ordinary local variable inside the method, so the loop can change it directly.
    3. Handle the even case. An even number has remainder 0 when divided by 2, so the test is n % 2 == 0. Then n = n / 2. Dividing two int values truncates the fraction, and the division is exact here because n is even.
    4. Handle the odd case in the else branch. Set n = 3 * n + 1. Any number that is not even is odd, so no second condition is needed.
    5. Print the new n after the else block, still inside the loop. This line runs for both branches, so each new term is printed once, right after it is produced.

    The solution in Java

    class Solution {
    public void printSeries(int n) {
        System.out.println(n);
        while (n > 1) {
            if (n % 2 == 0) {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
            System.out.println(n);
        }
    }
}

    A few Java notes:

    • Parameters are copies. Java passes int by value, so changing n inside the method does not affect the caller's variable. That is why reusing the parameter as the loop variable is safe.
    • Both branches print the same way. The println sits after the if/else, not inside each branch. Copying it into both branches also works, but a single line is easier to maintain.
    • The test is % 2 == 0. For positive numbers you could also write n % 2 == 1 for odd. Testing for even is safer in general, because in Java -7 % 2 is -1, not 1.

    Complexity

    The running time is the number of terms in the sequence. Nobody has a formula for it. It grows slowly, though: starting from 27 the sequence has 111 steps and climbs as high as 9232 before it falls to 1. The method stores nothing except the current number, so its extra space is O(1).

    Edge cases and common mistakes

    • Starting with 1. The output is just 1. The loop condition is false at once.
    • Printing in the wrong place. Without the first println, the output for 3 starts with 10. If the loop printed n at the top of its body instead of at the bottom, the final 1 would never appear, because the loop stops before it comes back to that line.
    • Using n >= 1 as the condition. This is an infinite loop. From 1 the odd rule gives 4, then 2, then 1 again, and the loop never ends.
    • Forgetting the else. With two separate if statements, an even number is halved and the second if then looks at the already-changed value, which can apply both rules in one pass.
    • Overflow with large starting values. The terms can grow well beyond the starting number, and an int stops at 2,147,483,647. Starting from 113383, the sequence reaches 2,482,111,348, which does not fit. After 120 steps the value wraps to a negative number, the condition n > 1 turns false, and the output stops at -1812855948. For large inputs, declare the variable as long.
    • Starting from 0 or a negative number. The conjecture is about positive integers. The method prints the starting value and stops at once, because the loop condition is false.

    Testing

    Try n = 3, which prints 3, 10, 5, 16, 8, 4, 2, 1. Try n = 1, which prints only 1, and n = 7, which prints 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

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