What is the most efficient way to find amicable numbers in python?

Question

I've written code in Python to calculate sum of amicable numbers below 10000:

def amicable(a, b):
   total = 0
   result = 0
   for i in range(1, a):
      if a % i == 0:
        total += i
   for j in range(1, b):
      if b % j == 0:
        result += j
   if total == b and result == a:
        return True
   return False

sum_of_amicables = 0
for m in range (1, 10001):
    for n in range (1, 10001):
        if amicable(m, n) == True and m != n:
            sum_of_amicables = sum_of_amicables + m + n

Code is running more than 20 minutes in Python 2.7.11. Is it ok? How can I improve it?

Answer 1

optimized to O(n)

def sum_factors(n):  
     result = []
     for i in xrange(1, int(n**0.5) + 1):
         if n % i == 0:
             result.extend([i, n//i])
     return sum(set(result)-set([n]))

def amicable_pair(number):
    result = []
    for x in xrange(1,number+1):
        y = sum_factors(x)
        if sum_factors(y) == x and x != y:
            result.append(tuple(sorted((x,y))))
    return set(result)

run it

start = time.time()
print (amicable_pair(10000))
print time.time()-start

result

set([(2620, 2924), (220, 284), (6232, 6368), (1184, 1210), (5020, 5564)])
0.180204153061

takes only 0.2 seconds on macbook pro

Answer 2

Lets break down the code and improve the parts of code that is taking so much time.

1-

If you replace if amicable(m, n) == True and m != n: with if m != n and amicable(m, n) == True:, it will save you 10000 calls to amicable method (the most expensive method) for which m != n will be false.

2- In the amicable method you are looping 1 to n to find all the factors for both of the numbers. You need a better algorithm to find the factors. You can use the one mentioned here. It will reduce your O(n) complexity to O(sqrt(n)) for finding factors.

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

Considering both the points above your code will be

def amicable(a, b):
    if sum(factors(a) - {a}) == b and sum(factors(b) - {b}) == a:
        return True
    return False

sum_of_amicables = 0
for m in range (1, 10001):
    for n in range (1, 10001):
        if m!= n and amicable(m, n) == True:
            sum_of_amicables = sum_of_amicables + m + n

This final code took 10 minutes to run for me, which is half the time you have mentioned.

---

I was further able to optimize it to 1:30 minutes by optimizing factors method.

There are 10000 * 10000 calls to factors method. And factors is called for each number 10000 times. That is, it calculates factors 10000 times for the same number. So we can optimize it by caching the results of previous factors calculation instead of calculating them at every call.

Here is how I modified factors to cache the results.

def factors(n, cache={}):
    if cache.get(n) is not None:
            return cache[n]
    cache[n] = set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    return cache[n]

Full Code: (Runtime 1:30 minutes)

So the full and final code becomes

def factors(n, cache={}):
    if cache.get(n) is not None:
            return cache[n]
    cache[n] = set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    return cache[n]

def amicable(a, b):
    if sum(factors(a) - {a}) == b and sum(factors(b) - {b}) == a:
        return True
    return False

sum_of_amicables = 0
for m in range (1, 10001):
    for n in range (1, 10001):
        if m!= n and amicable(m, n) == True:
            sum_of_amicables = sum_of_amicables + m + n

---

You can still further improve it.

Hint: sum is also called 10000 times for each number.

Answer 3

Note that you don't need to have a double loop. Just loop M from 1 to 10000, factorize each M and calculate sum of divisors: S(M). Then check that N = S(M)-M has the same sum of divisors. This is a straight-forward algorithm derived from the definition of an amicable pair.

There are a lot of further tricks to optimize amicable pairs search. It's possible to find all amicable numbers below 1,000,000,000 in just a fraction of a second. Read this in-depth article, you can also check reference C++ code from that article.

Answer 4

Adding to the answer:

def sum_factors(self, n):  
    s = 1
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            s += i
            s += n/i
    return s

def amicable_pair(self, number):
    result = 0
    for x in range(1,number+1):
        y = self.sum_factors(x)
        if self.sum_factors(y) == x and x != y:
            result += x
    return result

No need for sets or arrays. Improvinging storage and clarity.

Answer 5

#fetching two numbers from the user
num1=int(input("Enter first number"));
num2=int(input("enter the second number"));
fact1=[];
fact2=[];
factsum1=0;
factsum2=0;


#finding the factors of the both numbers
for i in range(1,num1):
    if(num1%i==0):
        fact1.append(i)


for j in range(1,num2):
    if(num2%j==0):
        fact2.append(j)

print ("factors of {} is {}".format(num1,fact1));
print ("factors of {} is {}".format(num2,fact2));
#add the elements in the list
for k in range(len(fact1)):
    factsum1=factsum1+fact1[k]

for l in range(len(fact2)):
    factsum2=factsum2+fact2[l]

print (factsum1);
print (factsum2);

#compare them
if(factsum1==num2 and factsum2==num1 ):
    print "both are amicable";
else:
    print "not amicable ";

this is my owm understanding of the concept

Answer 6

hi all read code and comments carefully you can easily understand

def amicable_number(number):

    list_of_tuples=[] 
    amicable_pair=[] 

    for i in range(2,number+1): # in which range you want to find amicable

        divisors = 1 # initialize the divisor

        sum_of_divisors=0 #here we add the divisors

        while divisors < i: # here we take one number and add their divisors

            if i%divisors ==0:   #checking condition of complete divison
                sum_of_divisors += divisors
            divisors += 1
        list_of_tuples.append((i,sum_of_divisors)) #append that value and sum of there divisors

    for i in list_of_tuples: 
                              #with the help of these loops we find amicable with duplicacy
        for j in list_of_tuples:
            if i[0] == j[1] and i[1] == j[0] and j[0] != j[1]: #condition of amicable number 

                amicable_pair.append((j[0],i[0])) # append the amicable pair

    # i write this for_loop for removing the duplicacy if i will mot use this for loop this
    # be print both (x,y) and (y,x) but we need only one among them
    for i in amicable_pair:

        for j in amicable_pair[1:len(amicable_pair)]: #subscript the list
            if i[0] == j[1]:
                amicable_pair.remove(i) # remove the duplicacy

    print('list of amicable pairs number are: \n',amicable_pair)

amicable_number(284) #call the function

Answer 7

Simple solution to find amicable numbers with loops

I found all the friendly pairs in 9 seconds using this algorithm:

sum_of, friendly, sum_them_all = 0, 0, 0
friendly_list = []

for k in range(1, 10001):
    # Let's find the sum of divisors (k not included)
    for l in range(1, k):
        if k%l == 0:
            sum_of += l
    # Let's find the sum of divisors for previously found sum of divisors
    for m in range(1, sum_of):
        if sum_of%m == 0:
            friendly += m
    # If the sum of divisors of sum of divisors of the first number equals 
    # with the first number then we add it to the friendly list
    if k == friendly and k != sum_of:
        if [sum_of, k] in friendly_list:
            continue
        else:
            friendly_list.append([k, sum_of])
    # Reset the variables for the next round
    sum_of = 0
    friendly = 0

# Let's loop through the list, print out the items and also sum all of them
for n in friendly_list:
    print(n)
    for m in n:
        sum_them_all += m
print(sum_them_all)

Full code runtime 10 seconds in Lenovo IdeaPad5 (Ryzen5)