Project Euler Problem #119

April 10, 2010

Read the details of the problem here

Summary

Investigating the numbers which are equal to sum of their digits raised to some power.

Solution

My first attempt at this was a simple brute force approach to try to find the numbers in order. I was dividing the log of the number by the log of the sum of the digits to get the power and then checking to see if this was an integer. This was working in principle but was obviously not going to scale up to finding the 30th term .

The next approach, which was successful, was to generate a set of base numbers raised to a range of powers and check them for matching the criteria, adding them into a result list when they did. In this way I was not certain of generating the numbers in order so have to search for more than specified then sort & select the required element.

def results = []

for (base in 2..200) {
    for (pow in 2..20) {
        def n = (base ** pow).toBigInteger()
        def sum = n.toString().toList().sum { it.toInteger() }
        if (sum == base) results << [ n, base, pow ]
        if (results.size() == 60) break
    }
}

results.sort { it[0] }

def answer = results[29][0]

This runs in 0.34 seconds. A Java version completes in 6ms – 56x faster.

This solution seems a little hacky though. The ranges were picked somewhat arbitrarily and the number of elements captured was also made sufficiently broad to try to make sure that the entry is captured in the list. (After some experimentation I found that by reducing the base range to 2..68 and the power range to 2..8 exactly 30 elements are collected, the final answer being the 28th found, and the runtime will reduce to 0.19 seconds.)

Conclusion

Groovy’s features were useful to provide a terse syntax but didn’t really add much to the creation of the solution. Performance was adequate for the scale of this problem.

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: