Skip to content

Project Euler Problem 71

January 13, 2012

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

From → Project Euler

One Comment

Trackbacks & Pingbacks

  1. Project Euler Problem 73 « In F# Major

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: