Problem 119

Comments

It took me a couple of tries to get this one. Instead of going bottom up, I went top down. I went through all numbers and all their powers, stopping at an upper limit of 10^15. But I knew that to add the digits in the base of these powers, the base must be at most 15*9. This made production of the number set really fast.

Then I checked all these numbers to see which of them fit the requirement, put those into another list, then found the 30th in the list.

Result

Script ran in under a second!

Code

def digadd(n):
	n = str(n)
	total = 0
	for d in n:
		total += int(d)
	return total


trys = set()
bound = 15
b = 1
while True:
	b += 1
	p = 1
	if b >= (bound+1)*9:
		break
	while True:
		p += 1
		this = b**p
		if this < 10**bound:
			trys.add((this, b))
		else:
			break

a = []
while len(trys) > 0:
	this = trys.pop()
	if digadd(this[0]) == this[1]:
		a.append(this[0])

print sorted(a)[29]