Project Euler Problem 33 Solution

Question

The fraction $\frac{49}{98}$ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that $\frac{49}{98} = \frac{4}{8}$, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, $\frac{30}{50} = \frac{3}{5}$, 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.

import Data.Ratio (denominator)

fraction :: Int -> Int -> Rational
fraction n d = fromIntegral n / fromIntegral d

curious :: Int -> Int -> Bool
curious n d | f > 1 = False
| d1 == 0 || d2 == 0 = False
| n == d = False
| n2 /= d1 = False
| otherwise = fraction n1 d2 == f
where f = fraction n d
(n1, n2) = quotRem n 10
(d1, d2) = quotRem d 10

main :: IO ()
main = print $denominator$ product [fraction n d | n <- [10..99], d <- [10..99], curious n d]
$ghc -O2 -o curious-fractions curious-fractions.hs$ time ./curious-fractions
real   0m0.003s
user   0m0.000s
sys    0m0.003s

Python

#!/usr/bin/env python
from fractions import *
from itertools import *
from functools import reduce

def is_curious(n, d):
f = Fraction(n, d)
if f >= 1:
return False
n_digits = [int(digit) for digit in str(n)]
d_digits = [int(digit) for digit in str(d)]

if n_digits[1] == d_digits[0]:
try:
if Fraction(n_digits[0], d_digits[1]) == f:
return True
except:
pass
return False
def main():
fractions = product(list(range(10, 100)), list(range(10, 100)))
print(reduce(lambda a, b: a * b, (Fraction(*f) for f in fractions if is_curious(*f))).denominator)

if __name__ == "__main__":
main()
$time python3 curious-fractions.py real 0m0.073s user 0m0.073s sys 0m0.000s Ruby #!/usr/bin/env ruby puts ('10'..'99').to_a.product(('10'..'99').to_a).select { |num, den| (num[0].to_f / den[1].to_f) == (num.to_f / den.to_f) && num[1] == den[0] && num[1] != den[1] }.uniq.map { |num, den| [num.to_i, den.to_i] }.reduce([1, 1]) { |p, v| f = [p[0] * v[0], p[1] * v[1]] [f[0] / f[0].gcd(f[1]), f[1] / f[0].gcd(f[1])] }[1] $ time ruby curious-fractions.rb
real   0m0.045s
user   0m0.044s
sys    0m0.000s