bancaldo™

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
How many different ways can one hundred be written as a sum of at
least two positive integers?

Analisi:
Stesso metodo del problema 31

python:

import time

START = time.time()

def eu_76(limit):
    qty = [0] * (limit + 1)
    qty[0] = 1
    for number in range(1,limit + 1):
        for i in range(number, limit + 1):
            qty[i] += qty[i - number]
    return qty[limit]

print "euler 76: {}".format(eu_76(100))
print time.time() - START

variante:

“Euler invented a generating function which gives rise to a recurrence equation in P(n)..”
La formula interessante é:

ne consegue che:

partitions = {}
def partition(n):
    if n < 0: return 0
    if n == 0: return 1
    if n not in partitions:
        # http://mathworld.wolfram.com/PartitionFunctionP.html
        partitions[n] = sum([(-1)**(k+1) * (partition(n - (k * (3 * k - 1) / 2))
            + partition(n - (k * (3 * k + 1) / 2))) for k in range(1, n+1)])
    return partitions[n]


print partition(100) - 1