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, *^{5}C_{3} = 10.

*In general,*

^{n}C_{r} = 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: ^{23}C_{10} = 1144066.

*How many, not necessarily distinct, values of *^{n}C_{r}, 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.

### Like this:

Like Loading...

*Related*

[…] previously blogged about this Project Euler puzzle nearly 6 years ago, using Python. This is my approach using PHP as a simple practical exercise for myself, and I’d […]

Pingback by Project Euler: problem 53 (PHP) – Combinatoric selections | Duncan's blog — October 18, 2014 @ 8:05 am |