Project Euler 14 別解

Q14.
コラッツ列が最も長い100万未満の自然数

まず、偶数で50万未満の場合、その2倍の数のほうが列が長いので考慮しなくてよい。
また、6n+4の形なら、2n+1→6n+4
また、6n+5の形なら、4n+3→12n+10→6n+5となるから、考慮しなくてよい。
また、6n+2の形なら、4n+1→12n+4→6n+2となるから、考慮しなくてよい。
以上を考慮すると速くなる。

def collatz(n):

    if (n & 1) == 0:

        n >>= 1

    else:

        n += n + n + 1

    return n
def get_collatz_length(n):

    length = 1

    while n > 1:

        n = collatz(n)

        length += 1

    return length
def is_removable(n):

    if (n & 1) == 0:

        if n < N / 2:

            return True

        return n % 6 > 0

    else:

        return n % 6 == 4
N = 1000000

max_length = 0

max_n = 0

for n in range(1, N):

    if is_removable(n):

        continue

    length = get_collatz_length(n)

    if length > max_length:

        max_length = length

        max_n = n
print max_n, max_length