Skip to main content

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:
  1. Prime numbers can never be amicable numbers. Think for yourself why it is so!
  2. A pair of amicable numbers are either both even or both odd.
  3. 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:
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
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😄.
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