There are exactly ten ways of selecting three from five, 12345:
In combinatorics, we use the notation, .
It is not until , that a value exceeds one-million: .
How many, not necessarily distinct, values of , for , are greater than one-million?
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.015s user 0m0.012s sys 0m0.000s
#!/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.030s user 0m0.020s sys 0m0.008s