Project Euler Problem #110

Read the details of the problem here

Summary

Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

Solution

Well now I see why this is one of the most popular search terms through which people find this blog. Having done Problem 108 which was recommended to do before attempting this one, I was hoping that I could just repurpose some of the code…and I could, to some extent, but (i) I couldn’t get it running in the time allowed as the assumptions I made regarding the start and the increments weren’t as straightforward to make for this problem so a more exhaustive search of the problem space was required and (ii) because I was doing a more exhaustive search I was hitting situations where the number couldn’t be factored into primes without creating a considerably larger prime list (or having many expensive isPrime() calls).

In other words, as I suspected, I just got lucky with the previous solution.

I did consider changing the divisors() function to deal with the latter case by simply failing & so ruling out the number if it couldn’t factor it with an “appropriate” number of smallish primes but it started to feel a little hackish. I backtracked a little on my reasoning for Problem 108 and got something working that is a little simpler, is more scalable across a larger search space, and is actually much neater in general though it does still rely on “educated” guesses for some of the bounds limiting values.

The solution to Problem 108 found the answer at 2² * 3² * 5 * 7 * 11 * 13, with the factors of the square of the answer being 2⁴ * 3⁴ * 5² * 7² * 11² * 13². The number of divisors was therefore 5*5*3*3*3*3 = 2025.

With the same logic as before we’d be looking for numbers whose square had at least 8 million divisors. Assuming that just squared factors were used that would need a number with up to around 14-15 prime factors as 3¹⁴ = 4,782,979, 3¹⁵ = 14,348,907.

I dithered around with these numbers for a while, trying different bases and increments as per my solution to Problem 108 but, as noted above, didn’t get anywhere.

I did some more reading of the forum for the previous problem.

Some people had solved it on paper just by “guessing” the values of the powers of the primes such that the number of solutions would exceed the limit and then working out the actual number from there, checking for closest proximity. This seemed eminently sensible and do-able in code. There was no need to factorize a number; the number of primes being inspected & the allowable powers could be easily tweaked to suit.

Based on the numbers above, the highest prime factor to be considered (assuming that the answer is likely going to be made up of higher powers of the lower primes) is 47. The range of powers I kicked off with would be from 0 (zero – meaning that that prime wasn’t a factor in the answer) to 5, which was fairly arbitrary in that I just doubled what the maximum was for Problem 108 and added 1 for luck…

def ( LIMIT, POWER_RANGE ) = [ 4e6, (0..5) ]
def primes =
    (2..47).findAll { it.toBigInteger().isProbablePrime(100) }

def gen_powers(range, maxlen, yield) {
  gen_powers(range, maxlen, [], yield)
}

def gen_powers(range, maxlen, pows, yield) {
  if (pows.size() == maxlen)
    yield(pows)
  else if (pows.size() == 0)
    range.each { gen_powers(range, maxlen, [it], yield) }
  else
    range.findAll { it >= pows[0] }
         .each { gen_powers(range, maxlen, [it]+pows, yield) }
}

def answer = Long.MAX_VALUE

gen_powers(POWER_RANGE, primes.size()) { powers ->
  if ((1 + powers.inject(1) { p, v -> p * (2 * v + 1) }).intdiv(2) >= LIMIT) {
    def n = 1G
    powers.eachWithIndex { v, i -> n *= primes[i] ** v }
    answer = [ answer, n ].min()
  }
}

This gave the correct answer in 1.13 seconds, so well within my 15 seconds cut off. After having determined what the answer was, and so what the real bounds were, I narrowed the search range as much as possible, and it ran inside 0.06 seconds.

Note: Having gained access into the forum, I wasn’t too surprised to see that some people had done this one with pencil & paper during an idle five minutes…

Conclusion

Groovy was good to do this in, providing listops to allow simple one-liners to be used to keep the code concise and the ability to easily pass a closure into a generator. Performance was adequate for the scale of solution.

It would be nice if the number promotion worked transparently though. I was left scratching my head again when n kept overflowing a Long that I was originally using before I realised I had to specify a BigInteger (the G suffix) instead. I guess it’s a trade-off between performance and ease-of-use but could prove to be a time-bomb in inadequately tested code.

Advertisement