Project Euler Problem 53 Solution

Question

There are exactly ten ways of selecting three from five, 12345:

123,124,125,134,135,145,234,235,245, and 345\displaystyle 123, 124, 125, 134, 135, 145, 234, 235, 245, \text{ and } 345

In combinatorics, we use the notation, 5C3=10^5C_3 = 10.

In general,

nCr=n!r!(nr)!, where rn,n!=n×(n1)×...×3×2×1, and 0!=1.\displaystyle ^nC_r = \frac{n!}{r!(n-r)!}, \text{ where } r \leq n, n! = n\times(n-1)\times...\times3\times2\times1, \text{ and } 0! = 1.

It is not until n=23n = 23, that a value exceeds one-million: 23C10=1144066^{23}C_{10} = 1144066.

How many, not necessarily distinct, values of nCr^nC_r, for 1n1001 \leq n \leq 100, are greater than one-million?

Haskell

choose :: Integer -> Integer -> Integer
choose _ 0 = 1
choose 0 _ = 0
choose n r = choose (n-1) (r-1) * n `div` r

main :: IO ()
main = print $ length $ filter (> 1000000) [n `choose` r | n <- [1..100], r <- [1..n]]
$ ghc -O2 -o combinatoric-selections combinatoric-selections.hs
$ time ./combinatoric-selections
real   0m0.019s
user   0m0.016s
sys    0m0.000s

Python

#!/usr/bin/env python
from gmpy2 import comb
count = 0
for n in range(1, 101):
    for r in range(1, n):
        c = comb(n,r)
        if c > 1000000:
            count += 1
print(count)
$ time python3 large-combos.py
real   0m0.026s
user   0m0.024s
sys    0m0.000s

Questions? Comments? Send me an email: [email protected]