Problem 23 Project Euler Solution with python

Non-abundant sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

I personally liked this problem because there were a lot of twists or ambiguities what ever you may want to call it. Let me break each of the misconceptions and explain algorithm.

First twists may be a question: Why did they tell us about Perfect Number when there was no use of it at all? There might be several reasons, in one aspect we can say that the extra information given is just to confuse you. In other aspect they might have given the extra information to say that if the sum of divisors of the number is greater than the given number then it called as abundant number, but not if the sum of divisors of the number is greater than or equal to the number.

Now the second thing. In question they have given the sum two abundant numbers as 12+12 and one might think that the sum is twice of each and every abundant number. But it is not so. lets say if we have abundant numbers below 20(for sake of simplicity) as 12, 18, 20 then the sum of two abundant numbers will be 12+12 = 24, 12+18 = 30, 12+20=32, 18+18=36,18+20=38, 20+20=40, so the sum of two abundant numbers will be 24,30,32,36,38,40.

Next thing in which I made a mistake was: It was a silly mistake. As we knew that our range was 28123, I thought if we will generate abundant numbers till 28123/2, the it would be sufficient, but in the real case you should understand that the sum of two abundant numbers: 28110 + 12 is also less than 28123. So my greediness for reducing the number of iterations was not possible.

Okay now you are aware of all the misconceptions and we will see the algorithm.

If you remember the divisors function which we have written in problem 21 solution, I am reusing the same function again in this program.

Next I am looping to store all the abundant numbers in a list.

After I have stored all the numbers in the list I using two loops in to generate the abundant sum and if the abundant sum is less than 28123, then I will invoke a statement. If the abundant sum is greater than 28123, then we will break the current loop and start the next loop(See the code to make a better sense of the algorithm).

Finally sum the list values to get the solution.

Program

Program which I wrote is as follows:

use with Gist Search You might get confused from line 34. Here I am assuming that all the numbers are not the sum of any two abundant numbers.

File: pep23.py ------------------------- #http://radiusofcircle.blogspot.com #time module for calculating execution time import time #square root from math module from math import sqrt #time at the start of execution start = time.time() #Function used from problem 21 def divisors(n): """This function will generate divisors of given number Example: divisors(28) will give [1,2,4,7,14]""" divs = [1] for i in xrange(2,int(sqrt(n))+1): if n%i == 0: divs.extend([i,n/i]) return list(set(divs)) #list to store the values of abundant numbers ab = [] #For loop to generate the abundant numbers for i in xrange(12,28123): if sum(divisors(i))>i: ab.append(i) #first let us assume all the numbers are #not sum of abundant numbers non_ab_sum = [x for x in xrange(28123)] #for loop to generate sum of two #abundant numbers for i in xrange(len(ab)): for j in xrange(i,28123): if ab[i]+ab[j] < 28123: #negating the value of the abundant sum non_ab_sum[ab[i]+ab[j]] = 0 else: break #printing the value of the sum of non abundant sum print sum(non_ab_sum) #printing the total execution time print time.time() -start

next in the for loop I am generating the abundant sum, as we have come to know that a number is abundant sum I am making its value to zero so that the number will not contribute any to the sum.

And all the remaining are simple.

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

Output

Summary

This problem was challenging in terms of framing a better performing algorithm rather than checking our programming skills. It took me many hours to find a better algorithm. I wouldn't say that this program is the best because it took more than 1 second(s) to execute. I have seen one of the best solutions on Stack Overflow - How to Optimize non abundant sums - algorithm written by Michael. But I didn't want to use the same code because, I wanted to share a different solution.

If you have any doubt or didn't understand anything or have a suggestion or have a better or different solution then please do comment to share it with the community.

You can also contact me.

Hope I have written this post in a uncomplicated and convenient way for you to understand easily.

Thank you. Have a nice day😃.

RADIUS OF CIRCLE

Search This Blog