# Project Euler Problem 70

Project Euler Problem 70 is kinda a mirror of the previous one, now we are to minimize **n/phi(n)**.

As for **n = p(1)*p(2)*…** where **p(i)** is prime **phi(n) = (p(1)-1)*(p(2)-1)*…** minimizing **n/phi(n)** would require least possible amount of as big as possible factors. As apparently one prime factor would not allow for **p** and **(p-1)** to be a permutation of each other, we’ll try to get away with two factors around **sqrt(10000000)**.

Interestingly, our persistence begins to pay back as we would be able to reuse code from Problem 4, Problem 10, and Problem 49 solutions for cartesian product of two lists, prime generator, and permutations recognition, respectively.

#nowarn "40" let rec primes = Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 } and nextPrime n = if isPrime n then Some(n, n + 2) else nextPrime(n + 2) and isPrime n = if n >= 2 then primes |> Seq.tryFind (fun x -> n % x = 0 || x * x > n) |> fun x -> x.Value * x.Value > n else false let arePermutes n m = let inline canonic n = new string (Array.sort ((string n).ToCharArray())) canonic n = canonic m let allPairs l1 l2 = List.map (fun x -> (List.map (fun y -> (x,y)) l2)) l1 |> List.concat let problem070() = let meanFactor = 10000000 |> (float >> sqrt >> int) let factors = primes |> Seq.skipWhile ((>) (meanFactor - 1000)) |> Seq.takeWhile ((>) (meanFactor + 1000)) |> Seq.toList allPairs factors factors |> List.filter (fun (x,y) -> x*y < 10000000 && arePermutes (x*y) ((x-1)*(y-1))) |> List.minBy (fun (x,y) -> float (x*y) / float ((x-1)*(y-1))) |> fun (x,y) -> x*y

We were lucky to get the right answer to the problem with this approach. Code itself is rather fast delivering the solution in around 70ms, although the size of the cartesian product of factors can be cut in half because of each pair of factors present in cartesian product twice.