아무 양의 정수 \(n\)에서 시작하자. \(n\)이 짝수면 \(2\)로 나누고, 홀수면 \(3n+1\)로 바꾼다.

$$ T(n) = \begin{cases} n/2 & (n \text{이 짝수}) \\ 3n+1 & (n \text{이 홀수}) \end{cases} $$

콜라츠 추측: 어떤 \(n\)에서 시작하든 이 과정은 언젠가 반드시 \(1\)에 도달한다.

1937년 제기된 이래 거의 90년째 미해결이다. 에르되시는 "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다"는 말과 함께 해결에 \(500\)달러를 걸었다. 현재까지 약 \(2^{68}\) 이하의 모든 시작값이 \(1\)에 도달함은 컴퓨터로 확인되었다.

추측이 거짓이려면 가능성은 둘뿐이다 — \(1\)을 포함하지 않는 순환(사이클)이 존재하거나, 무한히 커지는 발산 궤도가 존재하거나. 발산은 유한한 채점기로 검증할 수 없으므로, 이 문제는 전자를 요구한다.

\(1\)을 포함하지 않는 콜라츠 사이클을 하나 출력하라. 즉 서로 다른 양의 정수 \(a_1, \dots, a_k\) (\(k \ge 2\))로서 \(T(a_i) = a_{i+1}\) (\(1 \le i < k\))이고 \(T(a_k) = a_1\)이며, 어떤 \(a_i\)도 \(1\)이 아닌 수열이다. 채점기는 사이클 조건을 정확히 검증하며, 조건을 만족하는 어떤 사이클이든 정답으로 인정한다.

참고: 그런 사이클이 존재한다면 그 길이는 수십억을 넘는다는 사실까지는 증명되어 있다. 즉, 이 문제의 정답 출력은 그 자체로 수학사에 남을 발견이다.

유일하게 알려진 사이클 \(4 \to 2 \to 1 \to 4\)는 \(1\)을 포함하므로 인정되지 않는다. 그것도 받아 달라는 항의는 정중히 거절한다.

\(k \ge 2\). 모든 \(a_i\)는 서로 다른 양의 정수이며, \(a_i \ne 1\).

첫째 줄에 정수 \(0\)이 주어진다. 이 값은 무시해도 좋다 (이 문제에 실질적인 입력은 없다).

첫째 줄에 사이클의 길이 \(k\)를 출력한다.

둘째 줄에 사이클을 이루는 \(k\)개의 정수 \(a_1, \dots, a_k\)를 공백으로 구분해 출력한다. \(T(a_i) = a_{i+1}\), \(T(a_k) = a_1\) 순서여야 한다.

(형식 예시 — 만약 \(1\)이 허용됐다면 3 / 4 2 1이 사이클이다. 물론 허용되지 않는다.)

riseoj 작성

출처 Original