[Project Euler] Problem 14

원문: Problem 14

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개의 항을 가진 것으로 볼 수 있다. 비록 이것이 아직 증명 되지 않았지만 (Collatz 문제), 모든 숫자는 1로 끝난다고 생각할 수 있다.
백만 미만에서 시작하는 숫자 중에서 어떤 수가 가장 긴 사슬을 생성하는가?
참고: 단, 사슬은 백만보다 클 수 있는 항들을 생성한다.

Python

수학으로 간단히 하려고 하다가 모든 수들에서 대해서 생각하기로 했다.

>>> stack = {1:0}
>>> def search(n) :
    if n in stack :
        return (n, stack[n])
    else :
        if n%2==0 :
            return (n, stack.setdefault(n, search(n//2)[1]+1))
        else :
            return (n, stack.setdefault(n, search(3*n+1)[1]+1))
>>> max((search(x) for x in range(1, 1000000)), key=lambda x : x[1])

접기