Hier ist der Code in Python:

# function for pentagonal numbers
def pent (n):     return int((0.5*n)*((3*n)-1))

# function for generalized pentagonal numbers
def gen_pent (n): return pent(int(((-1)**(n+1))*(round((n+1)/2))))

# array for storing partitions - first ten already stored
partitions = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42]

# function to generate partitions 
def partition (k):
 if (k < len(partitions)): return partitions[k]

 total, sign, i = 0, 1, 1

 while (k - gen_pent(i)) >= 0:
  sign   = (-1)**(int((i-1)/2))
  total += sign*(partition(k - gen_pent(i)))
  i     +=  1

 partitions.insert(k,total)
 return total

Es verwendet diese Methode, um Partitionen zu berechnen:

p(k) = p(k − 1) + p(k − 2) − p(k  − 5) − p(k − 7) + p(k − 12) + p(k  − 15) ...

(Quelle: Wikipedia)

Bei großen Zahlen (über p (10 ^ 3)) nimmt der Code jedoch einige Zeit in Anspruch. Ich möchte Sie fragen, ob ich meinen Code optimieren oder auf einen anderen, aber schnelleren Algorithmus oder Ansatz hinweisen kann. Optimierungsvorschläge sind willkommen.

Und nein, bevor Sie fragen, ist dies nicht für Hausaufgaben oder Project Euler, sondern für den Erfahrungswert.