# Return all proper divisors of a number
def proper_divisors(n):
	return [x for x in range(1, (n/2)+1) if n % x == 0]

# Build a lookup table.  
# - Key is a number from 1 to size
# - Value is the sum of the proper_divisors of Key
def build_lookup_table(size = 10001):
	hash = {}

	for n in range(1, size):
		hash[n] = sum(proper_divisors(n))

	return hash

# Using the lookup table find amicable pairs
# An example of a amicable pair (200/284):
#  >>> proper_divisors(200) = 284
#  >>> proper_divisors(284) = 200
def find_amicable_pairs(table):
	pairs = []
	
	for n, sum_divisors in table.items():
		if table.has_key(sum_divisors) and table[sum_divisors] == n and sum_divisors != n:
			pairs.append((n, sum_divisors))

	return pairs


table = build_lookup_table(10001)

pairs = find_amicable_pairs(table)

# Since we have all the pairs, we just have to sum the first element
print sum([x for x,y in pairs])