Monday, 18 April 2016

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 ab, 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😄.

0 comments:

Post a Comment

Thank you for your interest. But to avoid spam, we will review your comment before it is published.

Follow by Email

Followers

Search This Blog

Translate

Feedback

Feedback - NEW

Categories

python (93) projecteuler.net (82) MATLAB (55) function (24) data (20) conversion (11) fprintf (11) documentatoin (9) input (9) Solutions (8) Stomy Attaway (7) help function (7) bottle (6) calculation (6) flask (6) colon operator (5) url (5) xlrd (5) algorithm (4) excel (4) figure (4) series (4) date formats (3) grades (3) requests (3) round function (3) triangle (3) Matlab applications (2) area (2) circle (2) clf (2) clock function (2) datetime (2) easy_install (2) f to c (2) for loop (2) interest (2) iterations (2) json (2) legend (2) load (2) marks (2) pip (2) plot (2) save (2) sharing (2) square (2) volume (2) weave (2) while loop (2) xlabel (2) ylabel (2) Bernoulli equation (1) Matlab vs Python (1) Pythagorean. triplet (1) abs function (1) account (1) append (1) approximation (1) ascii (1) bank (1) blogger (1) c to f (1) contribute (1) dishonesty (1) drive (1) eccentricity (1) ellipse (1) encoding (1) factorial (1) file (1) fixed point array power. power of a number (1) fluid flow (1) form (1) gcd (1) gosper (1) heap (1) kahan (1) kilometers (1) kilos (1) kph (1) meters (1) miles (1) moving_velocity (1) mph (1) multiplication (1) multiplication table (1) my thoughts (1) pairwise (1) part3 (1) part4 (1) part5 (1) polar to cartesian (1) pounds (1) pressure (1) principal (1) problem1 (1) problem10 (1) problem11 (1) problem12 (1) problem13 (1) problem14 (1) problem15 (1) problem16 (1) problem17 (1) problem18 (1) problem19 (1) problem2 (1) problem20 (1) problem21 (1) problem22 (1) problem23 (1) problem24 (1) problem25 (1) problem26 (1) problem27 (1) problem28 (1) problem29 (1) problem3 (1) problem30 (1) problem31 (1) problem32 (1) problem33 (1) problem34 (1) problem35 (1) problem36 (1) problem37 (1) problem38 (1) problem39 (1) problem4 (1) problem40 (1) problem41 (1) problem42 (1) problem43 (1) problem44 (1) problem45 (1) problem46 (1) problem47 (1) problem48 (1) problem49 (1) problem5 (1) problem50 (1) problem51 (1) problem52 (1) problem53 (1) problem54 (1) problem55 (1) problem56 (1) problem57 (1) problem58 (1) problem59 (1) problem6 (1) problem60 (1) problem61 (1) problem62 (1) problem63 (1) problem64 (1) problem65 (1) problem66 (1) problem67 (1) problem68 (1) problem69 (1) problem7 (1) problem8 (1) problem9 (1) pygments (1) pyramid (1) python notes (1) quickstart (1) quiz (1) read (1) rectangle (1) return (1) reynolds (1) selection (1) sitemap (1) sphere (1) stirlings (1) subplot (1) svg (1) temperature (1) third side (1) title (1) total_amount (1) transpose (1) unixtimestamp (1) urllib2 (1) velocity (1) virtualenv (1) wcf (1) weight (1) wind chill factor (1) write (1) xml (1)

License

Creative Commons License
Radiusofcircle by Anivarth Peesapati is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Based on a work at http://radiusofcircle.blogspot.com.
Permissions beyond the scope of this license may be available at Terms and conditions.
Scroll To Top