Home > Project Euler, python > Project Euler #53

Project Euler #53

There are exactly ten ways of selecting three from five, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.
In general,
nCr = n!/r!(n−r)!
,where r <= n, n! = n*(n-1)*...*3*2*1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
How many, not necessarily distinct, values of  nCr, for 1 <= n <= 100,
are greater than one-million?

python:

import time
from math import factorial as f

ts = time.time()

def extract(base, sel):
    return f(base)/(f(sel)*f(base - sel))

res = 0
for base in range(1, 101):
    for sel in range(1, base):
        ways = extract(base, sel)
        if ways > 10**6:
            res += 1

print "problem euler 53: {} \nelapsed time: {}sec".format(res, time.time() - ts)

Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: