Project Euler Problem 71 Solution
Consider the fraction, , where and are positive integers. If and , it is called a reduced proper fraction.
If we list the set of reduced proper fractions for in ascending order of size, we get:
It can be seen that is the fraction immediately to the left of .
By listing the set of reduced proper fractions for in ascending order of size, find the numerator of the fraction immediately to the left of .
prevFrac :: Int -> Int -> Int -> (Int, Int) prevFrac num den limit = inner 1 limit 1 where inner n d i | i == limit = (n, d) | den*m < num*i && m*d > n*i = inner m i (i+1) | otherwise = inner n d (i+1) where m = num*i `quot` den main :: IO () main = print $ fst $ prevFrac 3 7 1000000
$ ghc -O2 -o ordered-fractions ordered-fractions.hs $ time ./ordered-fractions real 0m0.012s user 0m0.008s sys 0m0.000s
#!/usr/bin/env python from fractions import Fraction def main(): three_sevenths = 3.0 / 7 closest = Fraction(three_sevenths).limit_denominator(1000000) while closest == Fraction(3, 7): three_sevenths -= 1e-6 closest = Fraction(three_sevenths).limit_denominator(1000000) print(closest.numerator) if __name__ == "__main__": main()
$ time python3 prop-frac.py real 0m0.030s user 0m0.024s sys 0m0.004s
Questions? Comments? Send me an email: [email protected]