Counting summations
Problem 76
It is possible to write five as a sum in exactly six different ways:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two positive integers?
def run(limit=100):
numbers_left = dict({limit: 1})
for a in range(limit - 1, 1, -1):
new_numbers_left = dict()
for b in numbers_left:
for c in range(0, b / a + 1):
left = b - c * a
new_numbers_left[left] = new_numbers_left.get(left, 0) + numbers_left[b]
numbers_left = new_numbers_left
x = list(numbers_left.values())
return sum(x)