Project Euler Solution 53: Combinatoric selections

Next in the series is Problem 53: Combinatoric selections where we have to evaluate binomials.

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, $\binom{5}{3} = 10$.

In gerenal, $\binom n r = \frac{n!}{r!(n-r)!}$, where $r \leq n$, $n! = n \cdot (n - 1) \cdot \ldots \cdot 3 \cdot 2 \cdot 1$, and $0! = 1$.

It is not until $n = 23$, that a value exceeds one-million: $\binom{23}{10} = 1,144,066$.

How many, not necessarily distinct, values of $\binom n r$ for $1 \leq n \leq 100$, are greater than one-million?

The problem here again is that programming languages without arbitrary large integers will have a problem pretty quickly. In Python we could just compute 100! = 93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000 and then divide out the denominator. We can write the binomial coefficient in a bit more clever way which will make it easier to avoid large numbers: $$ \binom n r = \frac{n!}{r!(n-r)!} = \frac{\prod_{i = n-r +1}^n i}{r!} \,. $$

This way we basically remove the $(n-r)!$ part from the $n!$ and just have the numbers $n \cdot (n-1) \cdot \ldots \cdot (n-r + 1)$.

We can then express this idea in code:

def solution() -> int:
    result = 0
    for n in range(1, 101):
        for r in range(1, n):
            coefficient = 1
            for factor in range(n, n - r, -1):
                coefficient *= factor
            for factor in range(2, r + 1):
                coefficient //= factor
            if coefficient > 1_000_000:
                result += 1
    return result

This then produces the correct result in 30 ms.