Project Euler Problem 77

gistfile1.txt

# http://projecteuler.net/problem=77
# i couldn't find a recursive generating function like i used for #76
# one exists, http://mathworld.wolfram.com/EulerTransform.html - but i couldn't figure it out
# so i had to go back to the change counting problem, #31, and repurpose one of those functions

for x in range (11,80):
	coins=[]
	
	# generate primes for coin algorithm
	n=x+1
	myPrimes = [True]*(n+1)
	last = 0
	for i in range (2,n):
		if myPrimes[i] == True:
			coins.append(i)
			j = 2*i
			while j<=n:
				myPrimes[j]=False
				j=j+i	
	coins.sort(reverse=True)
	 
	# this is one of the recursive coin algorithms for problem 31
	def foo (rest, i = 0):
		if i == len (coins) - 1:
			return rest % coins[i] == 0
		else:
			return sum (foo (rest - j*coins[i], i + 1)
						for j in xrange (rest / coins[i] + 1))
	
	print x,foo(x)