Problem 53 Project Euler Solution with python

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, ⁵C₃ = 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: ²³C₁₀ = 1144066.
How many, not necessarily distinct, values of  ⁿC_r, for 1 ≤ n ≤ 100, are greater than one-million?


This problem is also simple. There are few important points one has to consider before we can write a few for loops to solve the problem. You can call these points as algorithm also😊.

1) As you all know that two for loops required, one for n and one for r in ⁿC_r. According to the question the value of n(i.e first for loop) will start from 23 and end at 100. Value of r is discussed in (2).

2) The value of r in ⁿC_r will be in range of 4, n-4 i.e we can neglect the value of 0, 1, 2, 3, n-3, n-2, n-1, n. I have created my own proof for this one and here it goes:

ⁿC_r values r = 1,2,3

ⁿC_r values r = 4

As you can see from the above images that if we will take the values of r from 0,1,2,3,n-3, n-2, n-1, n, we will be in less than a million range. But the values can be in the range of 4 to n-4.

The same has been accomplished in the program. You can have a look at the program and you will for sure understand the program easily.

Program

I have used the inbuilt factorial function from math module.

for n in xrange(23, 101):
    for r in xrange(4,n-3):

xrange(a,b) generates all the numbers from a to b-1 and will not generate b. This is the reason why I have  used 101 instead of 100. This is the same reason why I have used n-3 instead of n-4 in the second for loop.

I think all the remaining things are simple enough.

You can download the source code from Github Gist pep53.py

Output

Answer: 4075
Execution time: 0.0272159576416 seconds
Output:

Project Euler Problem 53 output

Project Euler Problem 53 with answer

Summary

It just took me five minutes to write a solution for this problem. But I wanted to optimize my code and so I have printed all the iterations. Then I observed that the first three values and the last three values of a given n are always less than 1 million. Then I did some algebra and proved the result. This has optimized the code and had a very better performance. I am satisfied with the solution I have written. I don't know whether there is scope for improvement.

Please excuse me and correct me if my grammar is wrong or in an ambiguous way😃!

As always you can comment in the comment box if you have any doubt or didn't understand anything. I will be glad to help you.

Please don't hesitate to comment if you have found any typo or have a better program or have a different program, whatever programming language you might have used. Please do comment if you have any suggestion.

You can also contact me.

Thank you. Have a nice day😃!

Further reference: Math Captain - Combinations