Project Euler Problem #53

Problem #53 is one of the many problems in Project Euler that involves binomial coefficients. The question reads:

Project Euler Problem 53: Combinatoric selections
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 choose 3)=10.
In general, (n choose 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 choose 10)=1144066.
How many, not necessarily distinct, values of (n choose r) for 1≤n≤100, are greater than one-million?

My solution for this problem involves a bit of brute force. Here is my solution:

Solution #1: Brute Force Approach

We can rewrite the formula for n choose r in the more efficient form n choose r = n*(n-1)*(n-2)*…*(n-r+1)/r! Using this method, we can easily calculate n choose r for any values of n and r. Now, using the fact that Pascal’s Triangle is symmetric, i.e. n choose r = n choose n-r, we only have to check values of r from 0 to n/2 to determine the values of n choose r which are greater than 1,000,000. Checking all values of n between 1 and 100 and all values of r between 1 and 100, we can calculate a running total of the number of binomial coefficients in this range which are greater than 1,000,000. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #53
 '''
 
 import time
 
 def combination(n,r):
     numerator = 1
     denominator = 1
     for x in range(r):
         numerator*=(n-x)
         denominator*=(x+1)
     return numerator/denominator
 
 def projectEulerProblemFiftyThree(n, m):
     total = 0
     for c in range(1,n+1):
         for x in range(0,c/2+1):
             if(combination(c,x)>m):
                 total+=(c-2*x+1)
                 break
     return total
 
 start = time.time()
 print projectEulerProblemFiftyThree(100, 1000000)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 4075
 --- 0.000518083572388 seconds ---
 
 for input of n = 100, m = 1000000
 ''' 

And with that, we’re done. An alternative approach may use the fact that the sum of the numbers in the nth row is 2^n and instead find the sum of the numbers which are less than or equal to 1,000,000. This would probably be a more efficient approach for larger values of n. However, I am too lazy to implement it right now.

Thanks for reading!