This problem asks:

Given: Positive integers n and m with 0≤m≤n≤2000.

Return: The sum of combinations C(n,k) for all k satisfying m≤k≤n, modulo 1,000,000.

References

Restate the problem

I’m going to get two integers less than 2000. I need to find the sum of all the combination equations C(n, k) where k is between or equal to the two integers I get. This is going to be an extremely large number, so I need to return the answer modulo 1,000,000.

Solution steps

First, I used the formula from Wikipedia to count the number of possible combinations:

def comb(n, k):
    return (fact(n) // fact(k)*fact(n - k))

That code returned a value much higher than the correct response for the sample dataset.

I installed the math library and used math.comb(n, k) to calculate the number of combinations and got the correct result for the sample dataset.

I wasn’t content getting the correct answer using the math library, so I continued troubleshooting my own equation until I found that wrapping the denominator in parentheses fixed my equation as shown below.

def comb(n, k):
    return fact(n) // (fact(k)*fact(n - k))

Compare this code with the incorrect version above.

When I ran both my version and the math library version against Project Rosalind-sized datasets, my version reached the recursion limit trying to figure out the factorial for 1,689, while the math library version delivered the correct response on the first try.

Python concepts

The Python language puts a limit on the number of times a function can call itself to prevent stack overflow errors.

A stack overflow error happens when a program uses more memory on the call stack than is allocated, often due to excessive or infinite recursion. This can lead to program crashes or unexpected behavior as the stack runs out of space for new function calls.

It’s possible to change the recursion limit in Python with the sys.setrecursionlimit() function.

Post-solution notes

Challenges solved so far: 53

How many people solved this before me: 1,911

Most recent solve before me: two days ago

Time spent on challenge: 1 hour

Most time-consuming facet: My incorrectly implemented denominator in the comb function.

Questions from others: Most of the conversation in the Questions section was focused on getting languages other than Python 3 to handle such large integers.

Solutions from others: Everyone implemented the same equation.