Project Euler Problem #45

April 28, 2010

Read the details of the problem here

Summary

After 40755, what is the next triangle number that is also pentagonal and hexagonal?

Solution

Easy enough using Groovy to use a brute-force set-based approach. Just create three lists containing the numbers in the sets and then use the intersection method to whittle them down, remembering to remove the exemplar before taking the first element from the remainder. (I kept the exemplar in range to make sure the algorithm was working.)

def ( tri, penta, hexa ) = [ [], [], [] ]

for (n in 143L..<100000L) {
  tri   << (n * (n + 1)).intdiv(2)
  penta << (n * (3 * n - 1)).intdiv(2)
  hexa  <<  n * (2 * n - 1)
}

def answer =
    (tri.intersect(penta)
        .intersect(hexa)
        - [40755]
    )[0]

This runs in 0.79 seconds. The upper bound on the creation of the lists was somewhat arbitrary and, once the answer is known, can be reduced which obviously brings the runtime down.

Conclusion

Groovy made this quite simple to write by using the list set operators. Performance was adequate for the scale of the solution. Note that it’s important to use the Long (L) suffix on the numbers in the loop to prevent subsequent overflow in the bodies of the calculations.

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: