Problem Thirty

6 Dec

Here’s problem thirty:

Question: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

The trickiest part of this problem was determining a limit past which it is certain that no numbers can satisfy the conditions. The rest is more or less simple brute forcing and equality checking.

The limit can be found this way. It is impossible for a 9 digit number to be written as the sum of the fifth powers of its digits simply because the sum doesn’t reach that high. The lowest 9 digit number is 100,000,000, but the highest possible sum is 9*95 = 531441. Following this logic, 8 and 7 digit numbers are also impossible. However, a 6 digit number could potentially be written as the sum of the fifth powers of its digits: 100,000 < 6*95 = 354,294. Therefore, the largest number we need to test is 354,294 since any number after that will be impossible to reach with these sums.

Here’s the code:

result = 0

for x in range(2, 354295): # 6*9^5 + 1
	digits = [int(n)**5 for n in str(x)]
	if sum(digits) == x:
		result += x


The variable result is initialized to 0. We generate x‘s up until the limit, and find the fifth power of each of its digits using list comprehension. If the sum of these values is equal to the number itself, we add the number to the result. Once the loop finished the result is printed.

Answer: 443839


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: