Problem #72 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 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

The simplest way to solve this is to realize that its simply the sum of the euler totient (phi function) of all the numbers from 2 to 1,000,000. So we just need to generate some primes write a nifty totient function and run the numbers down.

Solution below in fSharp and requires the FSharp power pack and .Net 4.

#light

open System
open System.Diagnostics
open Microsoft.FSharp.Linq
open Microsoft.FSharp.Collections

//prime generation from
//http://bit.ly/aWFrGy
let is_prime_juliet n =
    let maxFactor = sqrt(float n)
    let rec loop testPrime tog =
        if testPrime > maxFactor then true
        elif n % testPrime = 0. then false
        else loop (testPrime + tog) (6. - tog)
    if n = 2. || n = 3. || n = 5. then true
    elif n <= 1. || n % 2. = 0. || n % 3. = 0. || n % 5. = 0. then false
    else loop 7. 4.

let getPrimes upTo =
    seq {
        yield 2.;
        yield 3.;
        yield 5.;
        yield! (7., 4.)
        |> Seq.unfold (fun (p, tog) -> if p <= upTo then Some(p, (p + tog, 6. - tog)) else None)
    }
    |> Seq.filter is_prime_juliet

let Primes =
    (getPrimes (1000.))
    |> Seq.toList

let rec factorise (n:float) =
    if n = 1. then
        []
    else
        let c = Primes |> List.filter (fun x -> n % x = 0.)
        if c.Length = 0 then
            [n]
        else
            let a = Primes |> List.find (fun x -> n % x = 0.)
            a :: factorise (n / a)

let Totient (x:float) =
    (factorise x)
    |> Seq.distinct
    |> Seq.map (fun x -> 1. - (1./x))
    |> Seq.fold(fun acc a -> acc * a) x

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

let Answer =
    [2. .. 1000000.]
    |> PSeq.map Totient
    |> PSeq.toArray
    |> PSeq.sum

Console.WriteLine(Answer)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore