Skip to main content

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.
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😃.
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more