Home > Project Euler, python > Project Euler #76

Project Euler #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
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 é:
Composition_number

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
Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: