Problem #53

This prob­lem over at Project Euler turned out to be a lot sim­pler than expected.  Forty-Three other prob­lems have been solved more times than this one; yet, it was dead sim­ple. Really, there is noth­ing inter­est­ing in its solu­tion, unlike Prob­lem #97 that I posted about yes­ter­day.

It’s straight com­bi­na­torics and fac­to­ri­als. So read the prob­lem page and be amazed at what a gimme this one is :)

Result: [snip]
Time: 0.321524143219

#!/usr/bin/python
import time
def fac­to­r­ial(n):
    if n > 1:
        return n * fac­to­r­ial(n–1)
    else:
        return 1

def com­bi­na­tions(r,n):
    return fac­to­r­ial(n)/(fac­to­r­ial(r)*fac­to­r­ial(n-r))

total = 0
start = time.time()
for n in range (1,101):
    for r in range(1, n+1):
        if com­bi­na­tions(r,n) > 1000000:
            total += 1
stop = time.time()
print “Result:”, total
print “Time:”, str(stop-start)

Leave a Reply