Problem 21 Project Euler Solution with python

Amicable numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.?

When I saw the title I initially thought that there would be a formula to generate amicable numbers, so that I can write a program for the given range and then find the solution. I searched on world wide web about Amicable numbers and found a few formulas, but till date we only have formulas which are capable of generating only few of amicable numbers but not all numbers in the given range.

Finally the solution was to write few for loops and based on the conditions, find the pairs. This was easy as we have already solved the previous problems.

Even though I didn't get any formula for amicable number, I found few interesting properties that amicable number have. They are:

Prime numbers can never be amicable numbers. Think for yourself why it is so!
A pair of amicable numbers are either both even or both odd.
A pair of amicable numbers are not the same numbers.

If you want to know more about amicable numbers then you can see:

I will explain you the concept behind the program before we continue to program.

As we know that amicable numbers can never be prime I have used the sieve of Eratosthenes that we have used in the problem 7. If you have solved the problem in any other way please have a look at the problem 7 solution page and have some understanding of the Sieve of Eratosthenes.

Next I have written a function to generate divisors of a number. so that as given in the question I will check for the condition and if the condition is satisfied then go ahead and save the number in the list for summation.

That's it this is the basic outline of the program. Now have a look at the program and I am sure you will understand it easily.

Program

The program is as follows:

File: pep21.py -------------- #http://radiusofcircle.blogspot.com #importing math and time modules import math,time #time at the start of the exucution start = time.time() #seive of Eratosthenes to generate prime numbers #https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes def sieve(n): is_prime = [True]*n is_prime[0] = False is_prime[1] = False for i in xrange(2,int(math.sqrt(n)+1)): index = i*2 while index < n: is_prime[index] = False index = index+i prime = [] for i in xrange(n): if is_prime[i] == True: prime.append(i) return prime #Function to generate divisors of a given number def divisors(n): divs = [1] for i in xrange(2,int(math.sqrt(n))+1): if n%i == 0: divs.extend([i,n/i]) return list(set(divs)) #prime number under 10000 primes = sieve(10000) #Amicable numbers ami_nums = [] #Numbers that are already checked checked = [] #Start checking for amicable numbers upto 10000 for i in xrange(2,10000): if i not in primes and i not in checked: da = sum(divisors(i)) db = sum(divisors(da)) checked.extend([da,db]) if i == db: if da != db: ami_nums.extend([i,da]) #printing the amicable numbers print 'Sum is {}'.format(sum(ami_nums)) #time at the end of execution end = time.time() #printing the execution time print end - start

I think you will only get confused on why I have used the square root in the divisors function. Let me explain it to you.

Consider any random number say 28 whose square root is 5.29 rounding it to next bigger integer we get 6. Now see the magic:

Divisors of 28 and iterations in python

As you can see there is no need to go beyond the square root of any number to get all of its divisors. Because of iterating till the square root of the number we have considerably reduced a large number of iterations.

A few peculiar cases made me use sets in python to give the output of the divisors of the number. One of the number is 16, when you follow above method you will get 1,2,4,4,8. So to remove duplicates we will use the sets in python.

If you want to download the source code then you can download it from Github Gist pep21.py.

Output

Summary

As we already knew sieve and others we were able to solve the problem very easily. Also this problem was somewhat challenging and I took some time to frame algorithm for this problem.

As always if you have any doubt or didn't understand anything or have any suggestion or comment, then please do comment in the comment box below and I will glad to help you.

Please don't hesitate to comment if I have made a typo or if you a different or better solution.

You can also contact me, if you want.

Thank you. Have a nice day😄.

RADIUS OF CIRCLE

Search This Blog