Problem #73 says:

Consider the fraction, n/d, where n and d are positive integers. If n

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

First off brute forcing this problem isn’t hard, and you can do it in well under a minute. However there is an elegant solution so readily available that it would be a shame not to go with it. The elegant method involves calculating a Farey Sequence (http://en.wikipedia.org/wiki/Farey_sequence) then counting the results. Alternatively we can just count how many results we would have without calculating the actual results.

Solution in f# and runs in ~.32 seconds. Requires .net 4 and fsharp.

#light
module ProjectEuler

open System
open System.Diagnostics

let watch = new Stopwatch()
watch.Start()

let rec FareySeq denom1 denom2 max =
    if (denom1+denom2) > max then
        0.0
    else
        1.0 + (FareySeq denom1 (denom1+denom2) max)+(FareySeq (denom1+denom2)denom2 max)

Console.WriteLine(FareySeq 3 2 12000)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.Beep() |> ignore
Console.ReadKey() |> ignore