Project Euler — Problem 69 Solution

Problem

Euler’s Totient func­tion, ?(n) [some­times called the phi func­tion], is used to deter­mine the num­ber of num­bers less than n which are rel­a­tive­ly prime to n. For exam­ple, as 1, 2, 4, 5, 7, and 8, are all less than nine and rel­a­tive­ly prime to nine, ?(9)=6.

image

It can be seen that n=6 pro­duces a max­i­mum n/?(n) for n <= 10.

Find the val­ue of n <= 1,000,000 for which n/?(n) is a max­i­mum.

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 answer = [2I..1000000I] |> List.maxBy (fun n -> double(n) / double(totient n))

Hav­ing bor­rowed a num­ber of func­tions I had used in pre­vi­ous solu­tions, the main func­tion of inter­est here is the totient func­tion. Going by the infor­ma­tion on Euler’s totient func­tion from wikipei­dia and math­world, the val­ue of the totient func­tion of n is be cal­cu­lat­ed using its prime fac­tors:

image

In words, this says that the dis­tinct prime fac­tors of 36 are 2 and 3; half of the thir­ty-six inte­gers from 1 to 36 are divis­i­ble by 2, leav­ing eigh­teen; a third of those are divis­i­ble by 3, leav­ing twelve coprime to 36. And indeed there are twelve: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35.

Which in essence is what the totient func­tion in my solu­tion is doing, except to avoid any round­ing errors it actu­al­ly mul­ti­plies the num­ber n by the prod­uct of the numer­a­tors before divid­ing by the prod­uct of denom­i­na­tors, i.e. 36 * (1 * 2) / (2 * 3) instead of 36 * 0.5 * 0.66666666667 which intro­duces a round­ing error which may or may not has an influ­ence in the result.

Update 2011/11/06:

This solu­tion takes a long time and doesn’t com­ply with the under one minute rule, by using a prime sieve like this one I was able to get the exe­cu­tion time down to under 50s on my machine.  Here is the revised code using the afore­men­tioned sieve imple­men­ta­tion:

Enjoy!