#### Problem

Euler’s Totient function, ?(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, ?(9)=6.

It can be seen that n=6 produces a maximum n/?(n) for n <= 10.

Find the value of n <= 1,000,000 for which n/?(n) is a maximum.

#### 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))

Having borrowed a number of functions I had used in previous solutions, the main function of interest here is the *totient* function. Going by the information on Euler’s totient function from wikipeidia and mathworld, the value of the totient function of n is be calculated using its prime factors:

In words, this says that the distinct prime factors of 36 are 2 and 3; half of the thirty-six integers from 1 to 36 are divisible by 2, leaving eighteen; a third of those are divisible by 3, leaving 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* function in my solution is doing, except to avoid any rounding errors it actually multiplies the number *n* by the product of the numerators before dividing by the product of denominators, i.e. 36 * (1 * 2) / (2 * 3) instead of 36 * 0.5 * 0.66666666667 which introduces a rounding error which may or may not has an influence in the result.

#### Update 2011/11/06:

This solution takes a long time and doesn’t comply with the under one minute rule, by using a prime sieve like this one I was able to get the execution time down to under 50s on my machine. Here is the revised code using the aforementioned sieve implementation:

Enjoy!

Pingback: Project Euler — Problem 72 Solution | theburningmonk.com()