콜라츠 수열

콜라츠 추측은 1937년에 로타르 콜라츠가 처음 제시한 수학 추측이고, 지금도 증명되지 않은 미해결 문제다. 이 과정에서 나오는 수열은 값이 구름 속 우박처럼 여러 번 오르내리기 때문에 우박 수열이라고도 부른다. 추측의 내용은 어떤 수에서 시작하든 반복하면 언제나 1에 도달한다는 것이다.

계산 규칙은 $3n + 1$ 문제라고도 하며, 다음과 같다.

1. 정수 $n$에서 시작한다.
2. $n$이 1이면 멈춘다.
3. $n$이 짝수면 $n$을 2로 나눈다. 그리고 2번으로 돌아간다.
4. $n$이 홀수면 $n$에 3을 곱하고 1을 더한다. 그리고 2번으로 돌아간다.

추측에 따르면 어떤 양의 정수에서 시작해도 이 과정을 반복하면 $n = 1$에 도달한다. 거쳐 간 값을 순서대로 늘어놓으면 $n$에서 1까지의 수열이 된다.

예를 들어 $n = 14$에서 시작하면 다음과 같이 진행된다.

• 14는 짝수이므로 다음 값은 $14 / 2 = 7$이다.
• 7은 홀수이므로 다음 값은 $3 \times 7 + 1 = 22$이다.
• 22는 짝수이므로 다음 값은 11이다.
• 11은 홀수이므로 다음 값은 34이다.
• 34는 짝수이므로 다음 값은 17이다.

값이 1이 될 때까지 이 과정을 이어간다.

시작값 $n$이 주어질 때 콜라츠 수열 전체를 출력하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 100\,000$)

$n$에서 시작해 1로 끝나는 콜라츠 수열을 공백 하나로 구분해 한 줄에 출력한다. 줄의 앞과 뒤에는 공백을 넣지 않는다.