Euler 78

gistfile1.txt

# http://projecteuler.net/problem=78
from math import floor,sqrt

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

def sign(x):
	a = floor(x/2)
	if a%2 == 0:
		return 1
	else:
		return -1

def p(k):
	if k in dict:
		return dict[k]
	elif k == 0:
		return 1
	elif k < 0:
		return 0
	elif k > 0:
		a=0
# it doesn't actually need to go all the way to the end of pents
# but when i tried to limit it to sqrt(k), it borked
		for x in range (1,len(pents)):
			a += sign(x-1)*p(k-pents[x])
		return a
		
pents = []
for a in range (-200,200):
	pents.append(pent(a))
	pents.sort()

dict = {}
for b in range (0,60000):
	dict[b]=p(b)
	if dict[b]%1000000==0:
		print b, dict[b]