Project Euler Problem 33 Solution

Question

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

We shall consider fractions like, 3050=35\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.

Haskell

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.000s

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.109s
user   0m0.100s
sys    0m0.004s

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.033s
user   0m0.032s
sys    0m0.000s

Questions? Comments? Send me an email: [email protected]