3n+1 문제

3n+1 문제 ( Link ) 라고 알려진 문제를 다룰 것이다. 콜라츠 추측 (모든 자연수가 3n+1 문제 규칙에 의해 1로 수렴할 것이라는 추측)이라고 알려진 이 문제는 좀 있다 살펴보겠지만 구현이나 검증하게 될 코드는 상당히 간단하다. 역시 컴퓨터는 반복 연산하는데는 도가 텄나보다 ㅎㅎ 아직까지 증명과 관련된 언급이나 뉴스가 안보이는걸 보면 추측으로만 남아있다보다. 이 문제를 처음 접했을 때는 고1 때 였다. 아마 이것의 응용 문제인, 자연수 2개를 받아서 그 숫자들 사이에 있는 모든 자연수 중에 3n+1 해답 수열의 길이가 가장 긴 숫자를 찾는 문제였던 걸로 기억한다. 찾아보니 문제 원문이 나오더라.

100_The_3n 1_Problem.pdf

이번엔 첨부한 pdf의 문제 자체를 풀기보단 그 전 단계인 3n+1 해답 수열 자체를 뽑아내는 것을 하려고 한다. 간단하니까...

---

[문제]

자연수 n을 입력받는다. 홀수인 경우 3n+1 을, 짝수인 경우 n/2를 연산한다. 1이 되면 연산을 멈추고 1이 아니면 다시 두번째 문장의 연산을 반복한다.

[예시]

입력: 3

출력: 3 10 5 16 8 4 2 1

입력: 101

출력: 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

입력: 27

출력: 27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

n = input('n? ')
while n > 1 :
    print n,
    if n%2 == 0:
        n /= 2
    else:
        n = 3*n+1
print n

입력받은 숫자로부터 1까지 어떻게 도착하는지 쭉 출력해보는 문제였다. 문제 원문과 같이 수열의 길이를 알고 싶었다면 3줄에서 print 로 출력하는 대신 count 변수를 만들어서 1씩 추가하는 방법을 쓸 수 있을 것이다. 무튼 원문에 나온 문제를 푸는 것은 숙제로 남겨두니까 각자 한 번 시도해보길 바란다. 위에 있는 코드 8줄 받아적는 시간에 이미 정답에 많이 접근할 수 있을 것이라 생각된다.

main(l){for(scanf("%d",&l);l>1;l=l%2?3*l+1:l/2)printf("%d ",l);printf("1\n");}

재미로 C코드로도 짜봤는데 옆으로 스크롤하면서 아무리 눈씻고 찾아봐도 띄어쓰기가 딱 한군데 밖에 없다. 게다가 변수도 해필 엘(l) 이라서 숫자 1이랑 구분하기도 어렵다. 가독성 따위 고려하지 않았다. ( 저 코드에 색깔이 없다고 생각해보라. ) printf가 두개인 것이 맘에 안드는데 능력자분들은 더 줄일 수 있지 않을까 생각해본다. 사람이 읽을 만한 친절한 버전의 C 코드는 아래에 첨부한다.

#include <stdio.h>
int main(void) {
    int n;
    scanf("%d",&n);
    while ( n > 1 ) {
        printf("%d ", n);
        if ( n%2 == 1 ) {
            n = 3*n + 1;
        } else {
            n = n/2;
        }
    }
    printf("%d\n", n);
    return 0;
}