My solution to Project Euler Problem 30.

Here’s the problem:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44

8208 = 84 + 24 + 04 + 84

9474 = 94 + 44 + 74 + 44

As 1 = 14 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.

**My Solution:**

# Author: Will Clausen # Date: 4/7/14 # Description: This file solves problem 30 for Project Euler import math # This function solves problem 30. Some noteworthy solution details include # using a list to go through the set of possible numbers. I used a list # because I wanted a way to easily obtain the next distinct permutation of # numbers with digits in increasing order from left to right. def problem30(): # Store the final sum in this variable final = 0 # Start by checking 11, because the numbers 1 through 10 are clearly # not going to meet the crtiteria of the problem. check = [0, 0, 0, 0, 1, 1] checkNum = listToNum(check) # This loop condition is an artifact of how I increment the number I am # checking (note that I check numbers in list form). Think of it as # saying, "while the number being checked is within the known limit of # possibilities" while check[0] != 10: # Get the sum of the fifth powers of the digits. digitSum = sumOfDigits(check) # Convert this sum into a list digitSumList = numToList(digitSum) helper = [] # Loop through the digits of the number being checked # to determine if the number being checked can be permuted # into its sum (in which case, we want to add that number to # the final sum). good = True for i in range(len(check)): if check[i] not in digitSumList: good = False break digitSumList.remove(check[i]) if good: final += digitSum # Move to the next number check = nextNum(check) checkNum = listToNum(check) return final # This function takes in a number in list form (base 10) and increments it # to the next number that has all its digits in increasing order from left to # right. def nextNum(numList): # The list must have length greater than 0 for # this function to make any sense assert(len(numList) > 0) # Start with the least significant digit, and work towards # the bigger numbers index = len(numList) - 1 # Increment the number numList[index] += 1 # If this causes the number to equal 10, update accordingly while numList[index] == 10: # If the last spot in the number list is now at 10 # that means there is nowehere left to increment, so # just terminate and return the messed up list if index == 0: break # Move the index to the left 1 index -= 1 # Demonstrate that ten 1's is equal to one 10 and add # accordingly. numList[index] += 1 # Here's where things get weird. In the while loop above, # note that some indices of numList will have tens in them # here's where we make those numbers make sense. In the problem, # it's not necessary to loop through every number, we only need to # loop through distinct permutations of numbers with a certain number # of digits. e.g. if we just checked 123, we have also checked # 132, 231, 213, 312, 321. This loop ensures that we get a new DISTINCT # number that we haven't checked before. It makes everything much faster. for i in range(index, len(numList)): numList[i] = numList[index] return numList # This function takes a number in list form, and converts it to integer form def listToNum(numList): # Start by taking the most significant digit num = numList[0] for i in range(1, len(numList)): # This ensures that the most significant digit ends up in the right # place. num *= 10 # Add the proper digit in the proper spot num += numList[i] return num # This function takes a number in integer form and converts it to list form. def numToList(num): # The easiest way to code this was to make the number a string... strNum = str(num) final = [0, 0, 0, 0, 0, 0] # ... then loop through the string and convert the character back to an # integer. I don't know if this is the most efficient way to do this, # but it was the solution that came to mind most quickly. for i in range(len(strNum)): final[len(final) - i - 1] = int(strNum[len(strNum) - i - 1]) return final # This function sums the fifth power of the digits in an input number def sumOfDigits(numList): final = 0 for i in range(0, len(numList)): final += pow(numList[i], 5) return final # Run the program to determine the solution. if __name__ == "__main__": answer = problem30() print "Answer: " + str(answer)