Problem 33 Project Euler Solution with Python

Digit cancelling fractions

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

This problem is very simple if you were to solve it with the help of python. In python you will have to use a module to deal with fractions. It is called fractions module. It is so simple to learn and you can see the documentation: fractions - Rational Numbers.

Please go and have a look at the official documentation and you will see its simplicity.

If you will understand the fractions module then you can directly have a look at the code, because there is no big algorithm to understand.

Program

As given in the question the value of the fractions which will have the given qualities have a value less than 1(denominator > numerator). The same can be seen in the second for loop.

File: pep33.py ------------------------- #http://radiusofcircle.blogspot.com #time module for calculation of execution time import time #importing fractions module from fractions import Fraction #time at the start of program execution start = time.time() #Product of all the four fractions say 1 for now product = 1 #'for' loops to generate Numerator and Denominator for i in xrange(10,100): for j in xrange(i+1,100): #Intersection of Two sets(Common number between the two) common = list(set(str(i))&set(str(j))) #Check if the list is not empty if len(common) != 0: #Check if the common number is not 0 if common[0] != '0': num = list(str(i)) den = list(str(j)) #Remove the common element from numerator num.remove(common[0]) #Remove the common element from Denominator den.remove(common[0]) #Check if the value of num and den are not equal to 0 if num[0]!='0' and den[0]!='0': #Check if they satisfy the question condition if Fraction(int(num[0]),int(den[0])) == Fraction(i,j): #multiply to the product product *= Fraction(i,j) #print the denominator of the resulting fraction print product.denominator #time at the end of program execution end = time.time() #Printing the total time for execution print end - start

I have used Python sets to find the common element and I am assuming that you should be familiar with everything if you have given a look at fractions module.

To perfectly understand the program I recommend you to take a few examples and substitute the values in the code to see what is happening in the background.

A few examples you will have to try are⁴⁹/_98,⁵⁹/_68,⁸⁹/_99,³⁰/_40,¹²/₂₀ .Try to evaluate each and every statement if it is necessary or not. Then I am sure you will for sure understand the code.

As always if you want to download the above source code then you can download it from Github Gist pep33.py

Output

Summary

This problem was relatively easy and I don't have any extra comments on this problem. I would have had any extra comments if I had not solved the problem with Python. Thanks to python, its inbuilt fraction module has helped me solve the problem easily.

If you have any doubt or didn't understand anything then comment in the comment box below and I will be glad to help you.

Please do comment if you have found any typo or have a better program or have a different program or have any suggestions. I will be glad to view each and every one of them.

You can also contact me.

Thank you. Have a nice day😃.

RADIUS OF CIRCLE

Search This Blog