Project Euler Problem #63

May 21, 2010

Read the details of the problem here

Summary

How many n-digit positive integers exist which are also an nth power?

Solution

The first thing was to determine the potential scope of the problem. The base number had to be 9 or less, as 10 (or above) to any power is going to have more digits than the power. Obviously 9 is going to have the highest possible power which is 1/(1-log(9)), which rounded down is 21, before having insufficient digits in the number.

   921 = 109418989131512359209,
   922 = 984770902183611232881.

So 922 only has 21 digits, therefore a power of 21 forms the upper search bound.

I was about to write a brute-force solution based on this when it struck me that all I actually needed to do was to sum up these maxima for the eligible bases i.e. 1-9, and not have to calculate the actual numbers themselves.

def answer =
    (1..9).sum { (int)(1 / ( 1 - Math.log10(it))) }

So it ended up just being a one-liner that runs in 28 ms.

Conclusion

Groovy listops made the solution very terse!

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: