Project Euler in F#: Problem 110

In the following equation xy, and n are positive integers.

\frac{1}{x} + \frac{1}{y} = \frac{1}{n}

What is the least value of n for which the number of distinct solutions exceeds four million?

This is “just” problem 108 on steroids. I put just in quotes because I was going to whip up a quick solution to this and then head out, and I ended up spending all day on this instead. Up until now, it’s taken longer to blog the solutions than come up with them, but this one took a ridiculously long time to solve.

Although this gives the correct answer, I feel like I’m giving up without having come up with a good solution by just filtering through all products of primorial numbers, but it’s nearly 4am, and I’m not going to be able to sleep unless I get some sort of solution. Oh well. That’s what I get for going after a problem that looked interesting. I should go through the forum post for this problem to see if I can learn how to solve this the right way. Maybe after I graduate and/or drop out of grad school :-).

    let factors n =
        let rec loop n m ms =
            if n % m = 0I then
                loop (n/m) m (m::ms)
            elif n > m then
                loop n (m+1I) ms
            else
                ms
        loop n 2I []

    let numFactors n = factors n |> Seq.countBy(fun x->x) |> Seq.map (fun (a,b) -> b+1) |> Seq.reduce(*)
    let numSolutionsTimesTwo n = numFactors (n*n)

    let ans = primorial |> Seq.find (fun n -> (numSolutionsTimesTwo n) > 8000000)

Just as an aside, I started working through project Euler problems because I missed programming. I’ve been doing all math all the time since starting grad school; I was hoping this would be a bit more programming intensive, but the higher numbered problems seem to be 99% math and 1% programming. I’ll work through more of the lower numbered problems, which will push me to learn more F# constructs without feeding into my grad school ennui, but I really ought to find a nice open source project to bang on.

Advertisements
Project Euler in F#: Problem 110

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