# Duncan's blog

## February 4, 2009

### Project Euler problem 53

Filed under: Project Euler,Python — duncan @ 12:00 am
Tags: , ,

Problem 53:

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,
nCr = n! / (r!(n-r)!)
where r <= n, n! = n*(n-1)*…*3*2*1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 <= n <= 100, are greater than one-million?

At first I looked at this and thought it was all about iterating through the combinations of digits, just like how it lists 123, 124, etc. Which sounds tricky. But it’s much simpler than that. In fact they give you the hardest part of the algorithm, the equation needed:
n! / (r!(n-r)!)

In Python this solution takes about 0.36 seconds. I’m going to start using the time module to calculate running times.

```import time
tStart = time.time()

values = 0

def factorial(x):
y = 1
for i in range(1,x+1):
y = y * i

return y

def calc(n, r):
return  factorial(n) / (factorial(r) * factorial(n-r))

for i in range(1,101):
for j in range(1, i):
if calc(i, j) > 1000000:
values += 1

print(values)
print("time:" + str(time.time() - tStart))
```

So, two functions, one calculates the factorial of x, the other just calculates our equation. The second function could instead have just been expressed as one line in our procedural code.

Then loop from 1 to 100. Within that, do an inner loop from 1 to whatever our current outer loop is on, passing the two loop counters into our function. We don’t really care which numbers produce values greater than a million; we only care how many numbers there are. So value is just a simple counter.