Project Euler 30, 31

30番
各桁を5乗して足すと同じになる数を求める
N桁の数の5乗和の最大値は
9^5*N

#!/usr/bin/env python
# -*- coding: utf-8 -*-

summary = 0
for i in range(2,9**5*6):
	right = 0
	left = i
	while left > 0:
		right += (left % 10)**5
		left /= 10
	if i == right:
		summary += i
print summary

31番
1,2,5,10,20,50,100,200ポンド硬貨でちょうど200ポンドは何通りできるか
再帰使うのがやっぱり楽かな

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def count_variety(sum_money,money_list):
	count = 0
	if money_list == [1]:
		return count + 1
	for i in range(0,sum_money/money_list[0]+1):
		new_money_list = money_list[:]
		if sum_money - i*money_list[0] == 0:
			count += 1
		elif sum_money - i*money_list[0] > 0:
			new_money_list.pop(0)
			count += count_variety(sum_money - i*money_list[0],new_money_list)
		else:
			break
	return count

money_list = [200,100,50,20,10,5,2,1]
print count_variety(200,money_list)