# Euler Solution 53

### From ProgSoc Wiki

# Solutions for Problem 53

Given the formula ^{n}C_{r} = n!/(r! (n - r)!) for calculating the number of ways to choose r elements out of a set of n elements (ignoring order), how many solutions are there to ^{n}C_{r} that are greater than 1000000 for n in the range 1..100?

## Haskell by SanguineV

Runtime: 128.73 ms

{- Define the factorial function -} fact :: Integer -> Integer fact 0 = 1 fact 1 = 1 fact n = n * (fact (n - 1)) {- Define the nCrMin function to return the list of values for which nCr is greater - than the minimum for some n. Ignore r = 0 and r = n as these are both 1. -} nCrMin :: Integer -> Integer -> [Integer] nCrMin n min = nCrMins where fn = fact n rs = [1.. (n - 1)] {- NOTE this line broken up for ease of reading -} nCrMins = filter (\z -> z > min) (map (\r -> floor ((fromIntegral (fn)) /(fromIntegral ((fact r) * (fact (n - r)))))) rs) {- Calculate the nCrs over the limit of 1000000 for n in the range 1 to 100, then - sum up the number of solutions for each n. -} main = print (sum (map (\x -> length (nCrMin x 1000000)) [1..100]))

There are some optimisations you can make to this based on values of n and r, possibly more than halving the runtime. I'm happy to discuss if anyone is curious?

## Python by Althalus

Runtime: 410 ms

import time #from math import factorial #Wrote it on my laptop, then ran it on Niflheim for speed comparisons... The factorial function is apparently only python 3. def factorial(n): r = 1 while n > 0: r*=n n-=1 return r start_time = time.time() def c(n,r): return factorial(n)/(factorial(r)*factorial(n-r)) counter = 0 for n in range(1,101): for r in range(0,n): if c(n,r) > 1000000: counter+=1 print(counter) run_time = time.time() - start_time print (run_time)