Problem #70 says:

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to 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.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10^(7), for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

For this problem we can take advantage of a nifty property of Euler’s totient. if we have a number that is the product of two(or more) primes such that P = J*K where J and K are Prime then the totient can be found with the formula φ(P) = (J-1)*(K-1). So we need a range of prime numbers that when we multiple the two highest numbers gives us a comfortable overhead on the maximum range we are checking. We then pair all of these numbers together by looping through them with two loops and by using two prime numbers to generate the number P we get the nifty totient function and we also maximize φ(P) by limiting the distinct factors of P.

Solution provided in f# requires .net4 and visual studio RC. Runs in about 4 seconds including prime generation.

#light

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

//prime generation from
//http://stackoverflow.com/questions/2053691/can-the-execution-time-of-this-prime-number-generator-be-improved
let is_prime_juliet n =
    let maxFactor = int64(sqrt(float n))
    let rec loop testPrime tog =
        if testPrime > maxFactor then true
        elif n % testPrime = 0L then false
        else loop (testPrime + tog) (6L - tog)
    if n = 2L || n = 3L || n = 5L then true
    elif n <= 1L || n % 2L = 0L || n % 3L = 0L || n % 5L = 0L then false
    else loop 7L 4L

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

let w = new Stopwatch();
w.Start()

let Primes =
    (getPrimes 5000L) 

w.Stop()
Console.WriteLine("Primes Generated in")
Console.WriteLine(w.Elapsed)

let Perm x y =
    (x.ToString().ToCharArray()
    |> Seq.sort
    |> Seq.toList) = (y.ToString().ToCharArray()
    |> Seq.sort
    |> Seq.toList)

Console.WriteLine("Starting Check")
let watch = new Stopwatch()
watch.Start()

let answer =
    let mutable num = 1L
    let mutable min = Decimal 100
    for j in Primes do
        for k in Primes do
            if (j <> k) then
                let i = j * k
                if i < 10000000L then
                    let totient = (j-1L)*(k-1L)
                    if (Perm i totient) then
                        if (Decimal i / Decimal totient) < min then
                            min <- (Decimal i / Decimal totient)
                            num <- i
    num

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