Combinatoric selections

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, ⁵C₃ = 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: ²³C₁₀ = 1144066.

How many, not necessarily distinct, values of  ⁿC_r, for 1 ≤ n ≤ 100, are greater than one-million?

---

Idea

Naive solution, as instructed.

---

import sys, os; sys.path.append(os.path.abspath('..'))
from timer import timethis
from math import factorial

def get_combinatoric(n, r):
    return factorial(n) // (factorial(r) * factorial(n -r))

get_combinatoric(5, 3)

10

@timethis
def solve():
    odd_cnt = 0
    for n in range(1, 101, 2):
        cnt = 0
        for r in range(n // 2 + 1):
            if get_combinatoric(n, r) > 1e6:
                cnt += 1
        odd_cnt += cnt * 2
        
    even_cnt = 0
    for n in range(2, 101, 2):
        cnt = 0
        for r in range(n // 2):
            if get_combinatoric(n ,r) > 1e6:
                cnt += 1
        even_cnt = even_cnt + cnt * 2 + (get_combinatoric(n, n//2) > 1e6)
    
    return odd_cnt + even_cnt

solve()

Run for 0.000 seconds

4075