princeofsudan

ProjectEuler#33 Digit canceling fractions

Apr 2nd, 2013
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.20 KB | None | 0 0
  1. #The fraction 49/98 is a curious fraction, as an inexperienced mathematician
  2. #in attempting to simplify it may incorrectly believe that 49/98 = 4/8,
  3. #which is correct, is obtained by cancelling the 9s.
  4.  
  5. #We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
  6.  
  7. #There are exactly four non-trivial examples of this type of fraction,
  8. #less than one in value, and containing two digits in the numerator and
  9. #denominator.
  10.  
  11. #If the product of these four fractions is given in its lowest common terms,
  12. #find the value of the denominator.
  13.  
  14. #See http://en.wikipedia.org/wiki/Anomalous_cancellation
  15. #See http://en.wikipedia.org/wiki/Euclidean_algorithm for finding the Greatest
  16. #Common Divisor.
  17.  
  18.  
  19. def gcd(a,b):
  20.     if b == 0:
  21.        return a
  22.     else:
  23.        return gcd(b,a%b)
  24.    
  25. fractions = []
  26. for i in range(10,99):
  27.     for j in range(i+1,100):
  28.         iStr,jStr = str(i),str(j)
  29.         if jStr[1] != '0' and iStr[1] == jStr[0] and \
  30.            float(iStr)/float(jStr) == float(iStr[0])/float(jStr[1]):
  31.             fractions.append((i,j))
  32.  
  33. numProduct = 1
  34. domProduct = 1
  35. for i in fractions:
  36.     numProduct *= i[0]
  37.     domProduct *= i[1]
  38.  
  39. print domProduct/gcd(numProduct,domProduct)
Advertisement
Add Comment
Please, Sign In to add comment