Python Implementation of Problem 53
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 53
Problem:
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?
1"""
2Project Euler Problem 53
3
4Problem:
5
6There are exactly ten ways of selecting three from five, 12345:
7
8123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
9
10In combinatorics, we use the notation, 5C3=10
11
12.
13
14In general, nCr=n!r!(n−r)!
15, where r≤n, n!=n×(n−1)×...×3×2×1, and 0!=1
16
17.
18
19It is not until n=23
20, that a value exceeds one-million: 23C10=1144066
21
22.
23
24How many, not necessarily distinct, values of nCr
25for 1≤n≤100, are greater than one-million?
26"""
27from .lib.math import n_choose_r
28
29
30def main() -> int:
31 answer = 0
32 for n in range(101):
33 for r in range(2, n-1):
34 if n_choose_r(n, r) > 1_000_000:
35 answer += 1
36 return answer