Project Euler 53

プロジェクトオイラー
http://projecteuler.net/index.php

Q53.
_nC_r(1≤n≤100)の100万を超える項の個数

ふつうにやると、こう。

from math import factorial
def combination(n, r):

    return factorial(n) / factorial(r) / factorial(n - r)
N = 100

M = 1000000

counter = 0

for n in range(1, N + 1):

    for r in range(0, n + 1):

        if combination(n, r) > M:

            counter += 1

print counter

これだと多倍長整数を使ってしまうので、パスカルの三角形を上から計算していき、100万を超えたら0を記録する。足し算をするどちらかが0でも0にする。そうして0を数える。

N = 100

M = 1000000
def comb(prev, n, i):

    if i == 0:

        return prev[0]

    if i == n:

        return prev[n-1]

    elif prev[i-1] == 0 or prev[i] == 0:

        return 0

    else:

        c = prev[i-1] + prev[i]

        if c > M:

            return 0

        else:

            return c
def count_exceed_M(C, n):

    C.append([ comb(C[n-1], n, i) for i in range(n + 1) ])

    return sum(map(lambda x: x == 0, C[n]))
counter = 0

C = [ [ 1 ] ]

print sum(map(lambda n: count_exceed_M(C, n), range(1, N + 1)))