Start learning free

LESSON 134 OF 338 · LOOPS & CONDITIONALS

Collatz Conjecture in Go: A Condition-Only for 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

Guided

Ctrl + Enter to check

GO · LOOPS & CONDITIONALS

Collatz Conjecture in Go, explained

Problem overview

The function printSeries receives an integer n and prints every value that n takes in the Collatz sequence. The rule is applied again and again: if the current number is even, the next one is half of it; if it is odd, the next one is three times it plus one. The sequence stops when it reaches 1, which every starting number tried so far eventually does, though nobody has proved that it always happens.

For n = 3 the output is one number per line: 3, 10, 5, 16, 8, 4, 2, 1. The starting value is printed first, then each new value as it is produced.

Approach: repeat a rule until a stopping value

The number of steps isn't known in advance, so a loop with a fixed count doesn't fit. The right tool is a loop that repeats while a condition holds: here, while n is greater than 1. Inside the loop, one step applies the even or odd rule to n and prints the new value.

The first value, the starting n, is printed before the loop. That way the output starts with the input and ends with the 1 that stops the loop. If n is already 1, the condition is false from the start, so the output is just 1.

Step by step

Print the starting value with fmt.Println(n). This is the first term of the series.
Write the loop. Go has no while keyword; a for with only a condition does the same job. for n > 1 { ... } repeats as long as n is greater than 1.
Handle the even case. Inside the loop, an if tests whether n % 2 == 0. If so, halve n. The parameter n is an ordinary local variable, so the function can change it directly.
Handle the odd case. The else branch runs exactly when n is odd. It sets n to 3 * n + 1.
Print the new value after the if/else, still inside the loop. Placed there, one print covers both branches.

The solution in Go

func printSeries(n int) {
    fmt.Println(n)
    for n > 1 {
        if n % 2 == 0 {
            n /= 2
        } else {
            n = 3 * n + 1
        }
        fmt.Println(n)
    }
}

Tracing n = 6 through the code gives 6, 3, 10, 5, 16, 8, 4, 2, 1: the first print outputs 6, then each pass of the loop moves to the next term and prints it.

Go details:

for is the only loop. A for with just a condition is Go's while. A bare for { } loops forever until a break or return.
Integer division truncates. / between two int values drops the remainder. Here it is applied only to even numbers, so nothing is lost.
Compound assignment. n /= 2 means n = n / 2. Go also has +=, -=, *= and %=.
Parameters are copies. Changing n inside the function doesn't affect the caller's variable, because Go passes arguments by value.
Braces on the same line. The opening brace of for, if and else must be on the same line as the keyword, and else must follow the closing brace: } else {.

Complexity

There is no simple formula for the number of steps. The sequence can rise before it falls: starting from 27, it takes 111 steps and climbs far above 27 before dropping to 1. So the running time depends on the input in an irregular way. Nobody has proved that the loop ends for every positive input, though it has been checked for enormous ranges of starting values. The space is O(1), since the function keeps only n.

Edge cases and common mistakes

n = 1. The function prints 1 and the loop never runs.
Powers of two. n = 8 prints 8, 4, 2, 1, because each step halves the number.
Forgetting the first print. The output would start from the second term, 10, for an input of 3.
Printing before the update. If the print is first in the loop, the final 1 is never printed, because the loop ends before the print can run.
Printing inside only one branch. Every term must appear, whether it was produced by the even rule or the odd rule.
Zero or negative input. The condition n > 1 is false, so only n is printed. The problem only considers positive integers.
Using if n % 2 == 1 for the odd test. That works for positive numbers, but for negative ones % gives -1, so else is the safer choice.

Testing

printSeries(3) prints 3, 10, 5, 16, 8, 4, 2, 1, one per line.
printSeries(1) prints 1.
printSeries(6) prints 6, 3, 10, 5, 16, 8, 4, 2, 1.

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

Start learning free