Project Euler 14

Question: 

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

이 수열은 총 10개의 항으로 구성된다. (13으로 시작해서 1로 끝나는) 증명되지는 않았지만 (콜라츠 문제), 어떠한 숫자로 시작해도 1로 끝나는 것을 알 수 있다.

그렇다면 100만보다 작은 수 중 어떤 숫자로 시작해야 가장 긴 콜라츠 수열을 얻을 수 있을까?

주의: 시작하는 숫자만 100만보다 작으면 된다. 콜라츠 수열 중간에 100만 이상이 되는 것은 문제없다.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

import time start = time.time() num = 5 result = [0,0] while num < 1e6:     nextnum = num     chain = list([num])        while chain[-1] != 1:         if chain[-1] % 2 == 0:             nextnum /= 2         elif chain[-1] % 2 == 1:             nextnum = 3*nextnum + 1         chain.append(nextnum)     if len(chain) > len(result):         result = chain     num += 2 print('The longest chain starts with: {}\nFound in {}s'.format(result[0],time.time() - start))   Colored by Color Scripter

cs

5 부터 시작해서 홀수 항으로 시작되는 수열들만 판별했다.

걸린 시간은 35.6s

837799