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에서 시작하여 1로 끝나는) 이 수열에는 10개 요소가 있음을 알 수 있다. 아직 이것이 증명되지는 않았지만(콜라츠 문제), 모든 숫자는 1로 끝나는 것으로 생각된다.
100만 미만 숫자 중 가장 긴 수열을 만드는 숫자는 무엇인가?
주의: 수열이 시작되면 1백만을 넘을 수 있다.
--------------------------------------------------------------------------
1에서 시작하여 반대방향으로 가는 형태로 접근해 봤는데 적절한 해결책을 찾아낼 수 없어서, 단순하게 1백만까지 반복해가면서 가장 길게 1을 구하는 수열을 찾는 형태로 해결하였다. 좀 더 빨리 답을 구할 수 있도록 개선할 방법이 있을 것 같은데 문제를 해결할 동안 떠오르지 않았다.
직관적으로는 모든 숫자가 1로 끝날 것 같은데 아직 증명되지 않은 추측이라 하니 수학의 세계는 생각보다 심오하다.