[Project Euler] 14. 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

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까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?

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

Click

다른 방법이 있을까 열심히 고민하다가 결국은 찾지 못하고 단순방식으로 결정하였습니다.
그나마 약간 이라도 시간효율을 줄이기 위해 이전 결과를 배열에 저장하여 콜라츠추측에 의해 수가 원래 수보다 작아지면 이전에 카운트한 수를 더해주는 방법을 택했습니다.

<script>
function p014_in(limit){
 var arr = new Array();
 arr[1] = 0;
 var max = 0;
 var seed = 0;
 for(var i=2; i<limit; i++){
  var cnt = 0;
  var temp = i;
  while(temp != 1){
   if(temp<i) break;
   else if(temp%2==0) temp /= 2;
   else temp = temp*3+1;
   cnt++;
  }
  arr[i] = cnt + arr[temp];
  if (max < arr[i]) {
   max = arr[i];
   seed = i;
  }
 } 
 result seed;
}
</script>