Project Euler Problem #44

April 28, 2010

Read the details of the problem here


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


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.


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.


Leave a Reply

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

You are commenting using your 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: