콜라츠의 추측(Collatz conjecture) 혹은 우박수 문제라고 불리는 이 알고리즘은 다음과 같습니다.

• 어떤 자연수 n이 입력된다.

• n이 홀수이면 3n + 1을 한다.

• n이 짝수이면 n / 2를 한다.

• n이 1이 될 때까지 2번과 3번 과정을 반복한다.

어떤 자연수 n이 주어졌을 때, 위 알고리즘에 의해 1이 되는 과정의 모든 수를 순서대로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n이 입력된다.

출력

n이 1이 될 때까지 거치는 과정을 한 줄에 하나씩 순서대로 출력한다.

제한 사항

• 1 ≤ n ≤ 10,000,000

• 3n + 1이 되는 과정에서 32비트 정수(int) 범위를 넘는 수는 입력으로 주어지지 않는다.

금지 키워드

• for

• while

• goto

One integer \(n\) (\(1 \le n \le 10^7\)).

Print the Collatz sequence, one number per line.

riseoj 작성

출처 Online Judge > GoldOJ