Project Euler — Problem 72 Solution

Problem

Con­sid­er the frac­tion, n/d, where n and d are pos­i­tive inte­gers. If n<d and HCF(n,d)=1, it is called a reduced prop­er frac­tion.

If we list the set of reduced prop­er frac­tions for d <= 8 in ascend­ing 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 ele­ments in this set.

How many ele­ments would be con­tained in the set of reduced prop­er frac­tions for d <= 1,000,000?

Solution

let hasDivisor(n) =
    let upperBound = bigint(sqrt(double(n)))
    [2I..upperBound] |> Seq.exists (fun x -> n % x = 0I)

let isPrime(n) = if n = 1I then false else not(hasDivisor(n))

// define the sequence of prime numbers
let primeSeq =
    Seq.unfold (fun state -> if state >= 3I then Some(state, state+2I) else Some(state, state+1I)) 1I
    |> Seq.filter isPrime |> Seq.cache

// define function to find the prime denominators for a number n
let getPrimeFactors n =
    let rec getPrimeFactorsRec denominators n =
        if n = 1I then denominators
        else
            let denominator = primeSeq |> Seq.filter (fun x -> n % x = 0I) |> Seq.head
            getPrimeFactorsRec (denominators @ [denominator]) (n/denominator)
    getPrimeFactorsRec [] n

let totient n =
    let primeFactors = getPrimeFactors n |> Seq.distinct
    n * (primeFactors |> Seq.map (fun n' -> n'-1I) |> Seq.reduce (*)) / (primeFactors |> Seq.reduce (*))

let f n = [2I..n] |> List.map totient |> List.sum
let answer = f 1000000I

This is almost iden­ti­cal to the solu­tion to prob­lem 69, with the excep­tion of the last two steps. Accord­ing to the infor­ma­tion on Farey sequence on wikipedia:

The Farey sequence of order n con­tains all of the mem­bers of the Farey sequences of low­er orders. In par­tic­u­lar Fn con­tains all of the mem­bers of Fn?1, and also con­tains an addi­tion­al frac­tion for each num­ber that is less than n and coprime to n. Thus F6 con­sists of F5 togeth­er with the frac­tions 1?6 and 5?6. The mid­dle term of a Farey sequence Fn is always 1?2, for n > 1.

From this, we can relate the lengths of Fn and Fn?1 using Euler’s totient func­tion ?(n) :

image

Giv­en that F1 = 0 in our case, F2 = 0 + totient 2, F3 = totient 2 + totient 3, and so on, and there­fore Fn = totient 2 + totient 3 + … totient n.