Skip to content

Instantly share code, notes, and snippets.

@rjmunro rjmunro/friendly.py forked from anonymous/friendly.py
Last active Dec 10, 2015

Embed
What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.