Collatz Sequence

The Collatz conjecture is a conjecture in mathematics that Lothar Collatz first proposed in 1937, and it is still unproven. The numbers it produces are also called a hailstone sequence, because the values rise and fall many times like hailstones in a cloud. The conjecture says that whatever number you start from, repeating the process always reaches 1.

The rule is also known as the $3n + 1$ problem, and it works like this.

1. Start with an integer $n$.
2. If $n$ is 1, stop.
3. If $n$ is even, divide $n$ by 2. Then go back to step 2.
4. If $n$ is odd, multiply $n$ by 3 and add 1. Then go back to step 2.

By the conjecture, starting from any positive integer and repeating the process reaches $n = 1$. Listing the values you pass through in order gives a sequence from $n$ down to 1.

For example, starting from $n = 14$ the process goes like this.

• 14 is even, so the next value is $14 / 2 = 7$.
• 7 is odd, so the next value is $3 \times 7 + 1 = 22$.
• 22 is even, so the next value is 11.
• 11 is odd, so the next value is 34.
• 34 is even, so the next value is 17.

You continue until the value becomes 1.

Given the starting value $n$, write a program that prints the whole Collatz sequence.

The first line contains an integer $n$. ($1 \le n \le 100\,000$)

Print the Collatz sequence that starts at $n$ and ends at 1 on one line, with the elements separated by a single space. Do not put a space at the beginning or the end of the line.