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.