Euler Solution 71

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 71

Note: this solution not linked from the main page.

From an ordered list of reduced proper fractions of the form n/d with d ≤ 1000000, find the numerator of the fraction immediately to the left of 3/7.

Haskell by SanguineV

Runtime: a second or two?

{- Given a numerator, denominator and limit, find the largest fraction below the
 - limit for that denominator by incrementing the numerator. Return the numerator
 - and denominator as a pair. -}
findFrac :: Double -> Double -> Double -> (Double,Double)
findFrac n d lim | (n + 1)/d >= lim = (n,d)
findFrac n d lim = findFrac (n + 1) d lim

{- Given a denominator, find the fraction that lies to the left of 3/7 with the
 - given denominator. -}
findIt :: Double -> (Double,Double)
findIt d = findFrac n d lim
  where
    lim = 3 / 7
    n = fromIntegral (floor (d * lim)) - 1

{- Given two pairs representing fractions, return the larger -}
pmax :: (Double,Double) -> (Double,Double) -> (Double,Double)
pmax (ln,ld) (rn,rd) | ln / ld > rn / rd = (ln,ld)
pmax _ r = r

{- Start with 2/5 as the known answer for d <= 8, then compare it to the max
 - for each denominator and return the resulting fraction as a pair. -}
main = print (foldl pmax (2,5) (map findIt [9..1000000]))
Personal tools