59 lines
1.3 KiB
Python
59 lines
1.3 KiB
Python
"""
|
||
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, (5 3) = 10 .
|
||
|
||
In general, (n r) = 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: (23 10) = 1144066 .
|
||
|
||
How many, not necessarily distinct, values of (n r) for 1 ≤ n ≤ 100 , are greater than one-million?
|
||
"""
|
||
|
||
import time
|
||
from functools import lru_cache
|
||
|
||
|
||
def timer(func):
|
||
def wrapper(*args, **kwargs):
|
||
start_time = time.time()
|
||
result = func(*args, **kwargs)
|
||
end_time = time.time()
|
||
elapsed_time = end_time - start_time
|
||
print(f"{func.__name__} time: {elapsed_time:.6f} seconds")
|
||
return result
|
||
|
||
return wrapper
|
||
|
||
|
||
def comfun(n, r):
|
||
return factorial(n) // (factorial(r) * factorial(n - r))
|
||
|
||
|
||
@lru_cache(maxsize=None)
|
||
def factorial(n: int, s: int = 1):
|
||
if n < s:
|
||
return 1
|
||
elif n == s:
|
||
if s < 1:
|
||
return 1
|
||
return s
|
||
else:
|
||
return n * factorial(n - 1)
|
||
|
||
|
||
@timer
|
||
def main():
|
||
num = 0
|
||
for i in range(1, 101):
|
||
for j in range(1, i + 1):
|
||
if comfun(i, j) > 1000000:
|
||
num += 1
|
||
print(num)
|
||
|
||
|
||
if __name__ == "__main__":
|
||
main()
|