콜라츠의 추측(우박수, 3n + 1) timer 1s memory 32MB

콜라츠 추측 (Collatz conjecture)은 1937년에 처음으로 이 추측을 제기한 로타르 콜라츠(Lothar Collatz)의 이름을 딴 것으로  3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불린다. 

콜라츠 추측은 임의의 자연수가 다음 조작을 거쳐 항상 1이 된다는 추측이다.

1. 짝수라면 2로 나눈다.

2. 홀수라면 3을 곱하고 1을 더한다.

3. 1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다.

예를 들어, 6 에서 시작한다면, 차례로 6, 3, 10, 5, 16, 8, 4, 2, 1 이 되어 8번 만에 1이 되고 수열의 길이는 9이다.

또, 27에서 시작하면 무려 111번을 거쳐야 1이 된다. 77번째에 이르면 9232를 정점으로 도달하다가 급격히 감소하여 34단계를 더 지나면 1이 된다.

이 추측은 컴퓨터로 20 × 2⁵⁸ 까지 모두 성립함이 확인되었다. 그러나, 아직 모든 자연수에 대한 증명은 발견되지 않고 있다. 

이 문제의 해결에 500달러의 현상금을 걸었던 에르되시 팔은 "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다."는 말을 남겼다.

출처 : wiki

해야 할 일(Task)

두 양의 정수 S, E(1 <= S <= E <= 1,000,000)을 입력받아 S에서 E까지 수 중에서 위와 같은 조작을 했을 때 가장 많은 단계수를 갖는 수열의 길이를 구하시오.

위 예제에서 6은 8단계를 거쳐 1이 되고 이때 수열의 길이는 9이다.