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