Project Euler Problem #29

February 14, 2010

Read the details of the problem here

Summary

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Solution

Maybe this was a challenging question back in Oct 2002 (or maybe not) when it was set but certainly not any more. A brute force approach with suitable collection class support makes this very easy.

def set = [] as Set

for (a in 2..100)
    for (b in 2..100)
        set << (a ** b)

def answer = set.size()

This runs in 0.49 seconds. Java does it in around 34 ms – a mere 14x faster showing that the majority of the work is being done in the Java collection and Maths classes.

Interestingly, replacing the for-loops with (2..100).each{} closures pushes the runtime out to 0.59 seconds. Using 2.upto(100){} closures gives a 0.56 second elapsed time. This 15% overhead is quite surprising given that most of the time would probably be spent in the set insertion.

Conclusion

Groovy made this a snap to write without the boilerplate overhead in Java. Adequate performance for the scope of the question.

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: