WCW

# Project Euler Problem 30

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 != 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)

# 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
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__":