24 lines
491 B
Python
24 lines
491 B
Python
from functools import lru_cache
|
|
|
|
|
|
@lru_cache(maxsize=1000000)
|
|
def possible_sums(n, n_orig, d):
|
|
if d == n_orig:
|
|
return 0
|
|
if n == 0:
|
|
return 1
|
|
if n < 0:
|
|
return 0
|
|
if d > n:
|
|
return 0
|
|
return possible_sums(n - d, n_orig, d) + possible_sums(n, n_orig, d + 1)
|
|
|
|
|
|
def euler_076():
|
|
return possible_sums(100, 100, 1)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e076.py: " + str(euler_076()))
|
|
assert(euler_076() == 190569291)
|