14. 3n+1

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

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

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

n → n/2 (n이 짝수일때)

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



이 규칙을 사용하여 13으로 시작하면 다음 수열을 얻을 수 있다:

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

13으로 시작한 수열은 10개의 수를 가진다.

아직 증명되진 않았지만 모든 수는 1로 끝날 것으로 생각된다.

100만 이하의 어떤수로 시작했을 때 가장 긴 수열을 갖는가?

주의 : 수열 시작후에 100만을 넘는 것은 허용된다.

한번 구해놓은 걸 다시 쓰면 빨리 끝납니다.

#include <stdio.h> #include <stdlib.h> int main() { long long i, j, cnt, *len, *max; len=(long long*)calloc(1000001, sizeof(long long)); len[1]=1; for(i=2; i<=1000000; i++) { for(cnt=0, j=i; ; cnt++) { if(j<=1000000) if(len[j])break; j = (j&1) ? (j*3+1) : (j>>1); } len[i]=cnt+len[j]; } for(max=len, i=0; i<=1000000; i++) { if(*max<len[i]) max=&len[i]; } printf("%d", max-len); free(len); }