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

Project Euler Problem 67 Solution with Python

Maximum path sum II By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3 That is, 3 + 7 + 4 + 9 = 23. Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
Read more

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 documenta...
Read more

Project Euler Problem 66 Solution with python

Diophantine equation ¶ Consider quadratic Diophantine equations of the form: $$ x^{2} – Dy^{2} = 1 $$ For example, when $D = 13$, the minimal solution in $ x $ is $ 649^{2} – 13 \times 180^{2} = 1 $ It can be assumed that there are no solutions in positive integers when $ D $ is square. By finding minimal solutions in $ x $ for $ D = {2, 3, 5, 6, 7} $, we obtain the following: $$ 3^{2} – 2×2^{2} = 1 $$ $$ 2^{2} – 3×1^{2} = 1 $$ $$ 9^{2} – 5×4^{2} = 1 $$ $$ 5^{2} – 6×2^{2} = 1 $$ $$ 8^{2} – 7×3^{2} = 1 $$ Hence, by considering minimal solutions in $ x $ for $ D ≤ 7 $, the largest $ x $ is obtained when $ D = 5 $. Find the value of $ D ≤ 1000 $ in minimal solutions of $ x $ for which the largest value of $ x $ is obtained.
Read more