Project Euler : Problem.14

양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.

n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)

13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)

그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?

참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.

규칙을 찾아보려고 했는데, hailstone sequence 로 검색을 해보니 아직까지도 연구가 되고 있는 수열인듯 했습니다. 처음엔 바이너리 트리로 구현을 해보려 했으나, 수행속도에 비해 트리 구현하는 시간이 훨씬 오래 걸릴 것 같아서 브루트 포스를 적용하였습니다. ( 실은 답이 너무 궁금했습니다. ) 후에 궁금해지면 트리를 구현 해봐야겠습니다.

포스팅 맨 아래에는 답이 있으므로, 원하지 않으시면 스크롤에 주의해주세요 :)

오류 1 : int 의 인식범위

 맨 처음에는 모든 숫자변수를 int 로 구현했습니다. C++의 int 범위는 -2,147,483,648 ~ 2,147,483,647 (약 21억) 정도인데, hailstone 그래프를 보면 20억보다 더 높이 치솟는 것을 볼 수 있습니다. 문제의 조건값 범위가 100만보다 훨씬 아래였다면 int 로도 무사히(?) 넘어갔을텐데, 이로 인해 변수타입의 범위에 대해 한번 더 경각심을 일깨우게 되네요.
 int로 구현하면, 범위 초과에 의해 답이 910107(475~6회 수행)이 나옵니다. 아무리 사이트에 답을 때려넣어도 "틀렸으니 재시도 바람" 이라는데, 코드는 아무리 봐도 정상인것 같을 뿐이고. 분명 어딘가 틀렸는데 어디가 틀린건지 알 수가 없었습니다. 결국엔 구글 검색을 해보았는데, 저와 같은 짓을 하신 분들이 꽤 계셨습니다 ㅋㅋㅋ 잠깐 동질감 느끼고, 얼른 변수형태를 바꿨습니다.

#include <iostream>
using namespace std;
int main(void)
{
    unsigned long int now = 1;      // 현재 연산 숫자
    int cnt = 0;                    // 연산수행 카운터
    unsigned long int nowMax = 0;   // 최다 연산수 숫자
    int cntMax = 0;                 // 최다 연산수
    unsigned long int tmpMax = 0;
    while ( now++ < 1000000 ) {
        cnt = 1;
        unsigned long int tmp = 0;  // 연산용 임시변수
        tmp = now;
        while(tmp > 1) {
            if ( tmp % 2 == 0 ) {
                tmp = tmp >> 1;     // 짝수이면 2로 나눔
            } else {
                tmp = tmp * 3 + 1;  // 홀수이면 n*3+1
            }
            if ( tmp > tmpMax ) tmpMax = tmp;
            cnt++;
        }
        if ( cnt > cntMax ) {       // 최다 연산수 확인
            cntMax = cnt;
            nowMax = now;
            cout << now << " " << cnt << " " << tmpMax << endl;
        }
    }
    cout << nowMax << " " << cntMax << endl;    // 출력
    return 0;
}

연산 도중 최대 값이 궁금하여 tmpMax를 삽입하였습니다.
위에 대한 출력은 다음과 같습니다.

2 2 1

3 8 16

6 9 16

7 17 52

9 20 52

18 21 160

25 24 160

27 112 9232

54 113 9232

73 116 9232

97 119 9232

129 122 9232

171 125 9232

231 128 9232

313 131 13120

327 144 13120

649 145 41524

703 171 250504

871 179 250504

1161 182 250504

2223 183 1276936

2463 209 1276936

2919 217 1276936

3711 238 1276936

6171 262 8153620

10971 268 27114424

13255 276 27114424

17647 279 27114424

23529 282 50143264

26623 308 106358020

34239 311 121012864

35655 324 121012864

52527 340 121012864

77031 351 593279152

106239 354 1570824736

142587 375 2798323360

156159 383 2798323360

216367 386 17202377752

230631 443 17202377752

410011 449 24648077896

511935 470 24648077896

626331 509 24648077896

837799 525 56991483520

837799 525

참조
자바스크립트 연산범위 참고 : http://lambdaexp.tistory.com/59
동일한 오류 (int범위 초과) : http://www.dreamincode.net/forums/topic/165403-project-euler-collatz-sequence/