Skip to content

Project Euler Problem 70

January 11, 2012

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.

Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: