Вот код в 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

Он использует этот метод для расчета разделов:

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

(источник:Википедия)

Тем не менее, код занимает довольно много времени, когда дело доходит до больших чисел (более p (10 ^ 3)). Я хочу спросить вас, могу ли я оптимизировать свой код или намекнуть на другой, но более быстрый алгоритм или подход. Любые предложения по оптимизации приветствуются.

И нет, прежде чем спросить, это не домашняя работа или проект Эйлера, а ценность для опыта.