Project Euler 53をPythonでやってみる

問題 53

解答

組み合わせ${}_n \mathrm{C} _r$は真ん中に行くにつれて大きくなっていくのでそれを利用しすると、各$n$に対して$r$を下から順に確認していき初めて1000000を超える$r$を見つけるとrからn-rまでは全て1000000以上となる。
これを利用して次のようなプログラムを組んだ。

ProjectEuler53.py

def factorial(n):
    if n==0: return 1
    prod = 1
    for i in range(1,n+1):
        prod *= i
    return prod

def check(n):
    for r in range(int(n/2)+1):
        c = factorial(n)/(factorial(r)*factorial(n-r))
        if c > 1000000:
            return n-2*r+1
    return 0


num_sum = 0
for n in range(1,101):
    num_sum += check(n)
print(num_sum)

0.088 seconds