Euler Solution 53

From ProgSoc Wiki

Jump to: navigation, search

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?

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)
Personal tools