Project Euler Problem #30:

Problem #30 concerns numbers which are equal to the sum of powers of their digits. The question reads:

Project Euler Problem 30: Digit fifth powers
Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4+6^4+3^4+4^4
8208 = 8^4+2^4+0^4+8^4
9474 = 9^4+4^4+7^4+4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

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

Once again, my solution for this problem falls into the category of “Brute Force”. In this case, I do want to return to this question eventually as I believe I can make it far more efficient. Here’s my solution:

Solution #1: Brute Force Approach

We place an upper bound on numbers that could have this property by calculating the smallest number of digits such that even if every one of that number of digits were a 9, the sum of the fifth powers of the digits would still be less than the number itself. From this, the upper bound is defined as that number of digits multiplied by 9^5. Once this upper bound is calculated, it is a simple task of checking every number between 2 and the upper bound inclusive. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #30
 '''

 import time

 def sumDigitPower(n,p):
     total = 0
     a = str(n)
     for x in a:
         total+=(int(x)**5)
     return total

 def projectEulerProblemThirty(p):
     a = 1
     while((10a) - 1 <= a(9p)):
         a+=1
     total = 0
     for x in range(2,(9p)a+1):
         if(x == sumDigitPower(x,p)):
             total+=x
     return total

 start = time.time()
 print projectEulerProblemThirty(5)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 443839
 --- 0.88481593132 seconds ---

 for input of p = 5
 '''

As shown above, even with a nice upper bound, the simple brute force solution takes nearly a second. Solving the same problem for sixth powers of digits takes roughly 10 seconds (Apparently the only number in that case is 548834). I would like to return to this question eventually to find a more efficient solution.

Thanks for reading! See you tomorrow.