This problem made me happy!

It turns out that some integers have the property that they are equal to the sum of their digits raised to some power. For example if we sum the digits in 81 we get 9. 9 raised to the power 2 is 81. Another example would be the number 1679616. The sum of the digits is 36. 36 to the power 4 is 1679616.

In this problem we are required to find the 30th term in the sequence of all the integers that have the property described above.

First Attempt

As I am a bear of very little brain, I started off with the worst possible approach. I tried to work through each of the integers in turn, calculate the sums of their digits and then test to see if that sum raised to any power returned the original integer. To my credit, it did occur to me to use logarithms to avoid checking every possible power. For example...

512 = 83

Therefore, log(512) / log(8) = 3. All I have to do is check to see if log(n) / log(sum) is an integer!

"Yep," I thought to myself, "that'll be much quicker. I am so smart! S-M-R-T, smart." As ever, hope turned to bitter disappointment. Even after I fixed the problem with floating point division (Python doesn't know that log(512) / log(8) is exactly 3).   

sequence = []
n = 11
while len(sequence) < 30:
  digits = list(str(n))
  sum, pwr = 0, 0
  for d in digits:
    sum = sum + int(d)
  if sum > 1:
    pwr = round(log10(n) / log10(sum),11)
    if pwr.is_integer():
      sequence.append(n)
      print(n)
  n = n + 1

This method sucked. It turns out that the integer we are looking for is of the order 1014. Working through all of the integers like this will take many years to deliver the result.

Second Attempt

I felt it was time to inject some thought into my Sunday afternoon. Not too much, mind you. I am bound to honour my sacred vow of physical and intellectual sloth.

Clearly, I needed to limit the search space. It occurred to me that if I started from the other end and worked backwards then there would be a lot less work to do. I took a wild guess at the size of the numbers that would be placed around the 30th position in the sequence. I didn't have much of an idea about this, but from looking at the results of my first attempt and working out that 909 is about 10 to the power 17 this seemed as good a limit as any. Armed this this randomly guessed upper limit I now had a plan.

1. Take each of the integers in the range 2 to 90 as bases.

2. For each of the bases, calculate values of the base raised to the powers in the range 2 to 10.

3. For each result from step 2, check to see if the sum of the digits was equal to the base.

4. If step 3 produces a positive result, add the base to a list.

5. Sort the list and print out the term in the sequence that we're looking for.

The advantage of this method is that it involves checking 704 different numbers rather then counting all the way up to somewhere above 100000000000000. An efficiency saving of nigh on 100%.  

sequence = []
for base in range(2,90):
  for exp in range(2,10): 
    n = base**exp
    digits = list(str(n))
    sum = 0
    for d in digits:
      sum = sum + int(d)
    if sum == base:
      sequence.append(n)

sequence.sort()
print(sequence[29])  

This code returns an answer in about 3 ms, well below the general project Euler target of 1 minute and very much smaller than the more forgiving targets that I set for myself.

On reflection, I think it should be possible to calculate upper bounds for the ranges of my bases and exponents. I, however, cannot be arsed with that.