Project Euler Problem #87

May 14, 2010

Read the details of the problem here

Summary

Investigating numbers that can be expressed as the sum of a prime square, cube, and fourth power?

Solution

Strictly speaking, I failed on this one. Groovy was taking just under 16 seconds to create a prime sieve for numbers up to 50 million and so I had to use Java to generate the sieve (a naive implementation taking 1.81 seconds).

Having got a set of primes it was then just a case of contructing three lists for the various powers of the primes and finding combinations that matched the criteria. As there are some duplicates possible it was necessary to store the results in a Set (again easy to do in Groovy) and just get the number of entries.

import com.keyzero.euler.EulerUtils

def LIMIT = 50000000
def powers = [ 2:[], 3:[], 4:[] ]
def sqrt = (int)Math.sqrt(LIMIT)
def primes = EulerUtils.getPrimes(sqrt)

for (i in 2..sqrt) {
  if (primes.isPrime(i)) {
    for (p in 2..4) {
      def n = i ** p
      if (n < LIMIT) powers[p] << n
    }
  }
}

def numbers = [] as Set

powers[2].each { p2 ->
  powers[3].findAll { (p2 + it) < LIMIT }.each { p3 ->
    powers[4].findAll { (p2 + p3 + it) < LIMIT }.each { p4 ->
        numbers << (p2 + p3 + p4)
    }
  }
}

def answer = numbers.size()

This runs in 5.36 seconds. Acceptable, but not the fastest of solutions, so maybe there’s a better way of approaching this problem. Switching over to an explicit set of nested loops (as code below) to process the prime power lists drops the runtime to 3.11 seconds. A reduction of 43% overall and 64% when excluding the sieve generation.

for (p2 in powers[2]) {
  for (p3 in powers[3]) {
    def p2p3 = p2 + p3
    if (p2p3 > LIMIT) break
    for (p4 in powers[4]) {
      def sum = p2p3 + p4
      if (sum > LIMIT) break
      numbers << sum
    }
  }
}

Conclusion

Groovy was a bit of a two-edged sword in this solution. It’s lack of raw performance meant that I had to import some Java (which was easy to do though) but it’s listops made the rest easy to do, albeit not very performant. This solution shows again that using listops is convenient but carries a high runtime performance penalty.

Advertisements

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: