Euler Problem 76

gistfile1.txt

# http://projecteuler.net/problem=76
# we'll use euler's formula for generating the partition series

def pent(n):
	return ((3*n*n)-n) / 2

def p(k):
	if k in dict:
		return dict[k]
	elif k == 0:
		return 1
	elif k < 0:
		return 0
	elif k > 0:
		return p(k-pents[1])+p(k-pents[2])-p(k-pents[3])-p(k-pents[4])+p(k-pents[5])+p(k-pents[6])-p(k-pents[7])-p(k-pents[8])+p(k-pents[9])+p(k-pents[10])-p(k-pents[11])-p(k-pents[12])+p(k-pents[13])+p(k-pents[14])-p(k-pents[15])-p(k-pents[16])+p(k-pents[17])+p(k-pents[18])
		
			
pents = []
for a in range (-10,10):
	pents.append(pent(a))
	pents.sort()

dict = {}
# dictionaries are really important for fast recursion- otherwise you recalculate items multiple times
for b in range (0,101):
	dict[b]=p(b)
# here you're looking for 1 less than partition(b), b/c we're not including partitions with a single item
	print b,dict[b]-1