Problem Description

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 8³ = 512. Another example of a number with this property is 614656 = 28⁴.

We shall define a_n to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a₂ = 512 and a₁₀ = 614656.

Find a₃₀.

Analysis

Taking advantage of the easy large integer support in Python, we iterated two loops representing the base and exponent with the intention of accommodating inquiries up to a₂₀₀. Ignoring a^b values < 10 it was a simple process of adding the digits of the powers and comparing that sum to the base. After collecting relevant values into an array, it was sorted and the proper index printed for the answer.

Solution

Runs < 1 second in Python.

def sum_of_digits(n):
  return sum(map(int,str(n)))
 
a = []
n = 30  #tested up to n = 220
for b in xrange(2, 600):
  for e in xrange(2, 50):
     p = b**e
     if sum_of_digits(p) == b: a.append(p); 
     if len(a)>n*1.1: break
a.sort()
print "Answer to PE119 = a(%d) =" % n, a[n-1]

Comments

The base index of arrays in Python begin with 0. We need to subtract one from our index because the problem is using a base of 1; a₃₀ = a[29].
We provide an early escape when we have calculated enough values to provide the result for the given index.