friendly.py

def memoize(f):
	cache= {}
	def memf(*x):
		if x not in cache:
			cache[x] = f(*x)
		return cache[x]
	return memf

@memoize
def sum_factors(x):
	# Factors are either less than the square root and paired with a number
	# greater than the square root, or the square root itself
	sum = 1
	j = 2
	square = 4
	# Find factors less than the square root
	while square < x:
		if x%j==0:
			sum += j
			sum += x/j
		# Find next square using: (x + 1)**2 = (x**2 + 2*x + 1)
		square += j + j + 1
		j += 1
	# Add the square root itself
	if square == x:
		sum += j
	return sum

def friendly_numbers(limit):
	for n in range(1,limit):
		friend=sum_factors(n)
		friendliest=sum_factors(friend)
		if n==friendliest and n!=friend:
			print n, "and", friend, "are besties!"

friendly_numbers(5000)