Project Euler Problem #44

April 28, 2010

Read the details of the problem here

Summary

Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.

Solution

Straightforward enough to do, but I ended up having to use Java arrays rather than Groovy lists as performance of the latter was so bad in this scenario. All I do is to create a list of pentagonal numbers and then try to find pairs that match the criteria, preserving the best difference when I find a match. I tried several runs, extending LIMIT on each, until I got an answer.

def ( LIMIT, answer ) = [ 2500, Integer.MAX_VALUE ]
def penta = new int[LIMIT+1]

for (n in 1..LIMIT) {
  penta[n] = (n * (3 * n - 1)).intdiv(2)
}

for (i in 1..<LIMIT) {
  def pi = penta[i]
  for (j in i+1..LIMIT) {
    def pj = penta[j]
    def diff = pj - pi
    if (   (diff < answer)
        && (Arrays.binarySearch(penta, diff) > 0)
        && (Arrays.binarySearch(penta, pi + pj) > 0))
    {
        answer = diff
    }
  }
}

This runs in 3.60 seconds. A Java version takes 273 ms – only 13x faster as much of the work is being done in the Arrays class library in both cass.

Conclusion

I wasn’t able to use Groovy’s lists and listops here are the performance was absolutely dreadful. An equivalent version of this solution using such features had a runtime of 70 seconds.

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: