# Solutions for Problem 53

Given the formula nCr = 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 nCr that are greater than 1000000 for n in the range 1..100?

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)
```