Pascals Padlock

After a couple of weeks hiatus from programming; relaxing on the beautiful beaches of Crete, I have returned to my independent progression in programming and maths with a great new problem.

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 & 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?

** where the notation 5C3 represents 5 choose 3 in combinatorics

This stuck out to me as an interesting problem as there are different solutions, and so those of you that would like to attempt it, feel free to post your solutions below in the comments!

SPOILER ALERT…this is how I solved the problem. Let’s break down the problem and try to visualise what we are trying to do.

So as the example states lets imagine we have cards numbered 1 to 5, and you pick 3 at a time to create a 3 digit number. However, we need to be clear we are looking at combinations rather than permutations, hence the order of the numbers are disregarded. Using the same principle we can develop a simple algorithm to solve the problem simply using the formula for nCr and any value above or equal to 1 million will be added to the count.

Function:

• create a function that calculates n choose r
• create a variable that has a count of 0
• find nCr for values between 23 and 101 that are greater than 1 million *we can do it between 23 and 101 because any value below 23 will be below 1 million*
• for every nCr between 23 and 101 that is greater than 1 million is added to the total count.
• print the count and time taken

I believe we could even speed up the output time by using pascals triangle or the binomial coefficient to reduce the number of values in our array. Stay tuned on my page to see if I try tackle this problem again !