# Project Euler Problem 71

Project Euler Problem 71 all of a sudden allows for a “quick and dirty” solution. Here are some prelude considerations:

`we are looking for max(n/d) < 3/7, where d >= 1, d <= 1000000, n<d, HCF(n,d)=1.`

n/d < 3/7 **=>**

7*n < 3*d **=>**

7*n <= 3*d - 1 **=>**

n <= (3*d - 1)/7

Hence max(n) = (3*d - 1)/7. Of these pairs (n,d) for d below 1000001 we need such one that yields maximum (n/d), this will be the closest to 3/7.

The following “one-liner” does the trick:

let problem071() = [1..1000000] |> List.map (fun x -> ((3 * x - 1) / 7), x) |> List.maxBy (fun (x,y) -> (float x) / (float y)) |> fst

Apparently, performance is nothing to be proud of, but still it is around 500ms and brevity of the solution is a clear plus.

Advertisements

## Trackbacks & Pingbacks