My solution to Project Euler Problem 30.<\/p>\n
Here’s the problem:<\/p>\n
Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:<\/p>\n
1634 = 14 + 64 + 34 + 44
\n8208 = 84 + 24 + 04 + 84
\n9474 = 94 + 44 + 74 + 44
\nAs 1 = 14 is not a sum it is not included.<\/p>\n
The sum of these numbers is 1634 + 8208 + 9474 = 19316.<\/p>\n
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.<\/p>\n
My Solution:<\/strong><\/p>\n 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 + […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[29,28,42],"class_list":["post-118","post","type-post","status-publish","format-standard","hentry","category-project-euler","tag-digit-fifth-powers","tag-problem-30","tag-project-euler"],"_links":{"self":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/118","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=118"}],"version-history":[{"count":1,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/118\/revisions"}],"predecessor-version":[{"id":119,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/118\/revisions\/119"}],"wp:attachment":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=118"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=118"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=118"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\r\n\r\n# Author: Will Clausen\r\n# Date: 4\/7\/14\r\n# Description: This file solves problem 30 for Project Euler\r\n\r\nimport math\r\n\r\n# This function solves problem 30. Some noteworthy solution details include\r\n# using a list to go through the set of possible numbers. I used a list\r\n# because I wanted a way to easily obtain the next distinct permutation of\r\n# numbers with digits in increasing order from left to right.\r\ndef problem30():\r\n # Store the final sum in this variable\r\n final = 0\r\n\r\n # Start by checking 11, because the numbers 1 through 10 are clearly\r\n # not going to meet the crtiteria of the problem.\r\n check = [0, 0, 0, 0, 1, 1]\r\n checkNum = listToNum(check)\r\n\r\n # This loop condition is an artifact of how I increment the number I am\r\n # checking (note that I check numbers in list form). Think of it as\r\n # saying, "while the number being checked is within the known limit of\r\n # possibilities"\r\n while check[0] != 10:\r\n # Get the sum of the fifth powers of the digits.\r\n digitSum = sumOfDigits(check)\r\n\r\n # Convert this sum into a list\r\n digitSumList = numToList(digitSum)\r\n helper = []\r\n\r\n # Loop through the digits of the number being checked\r\n # to determine if the number being checked can be permuted\r\n # into its sum (in which case, we want to add that number to\r\n # the final sum).\r\n good = True\r\n for i in range(len(check)):\r\n if check[i] not in digitSumList:\r\n good = False\r\n break\r\n digitSumList.remove(check[i])\r\n if good:\r\n final += digitSum\r\n\r\n # Move to the next number \r\n check = nextNum(check)\r\n checkNum = listToNum(check)\r\n\r\n return final\r\n\r\n# This function takes in a number in list form (base 10) and increments it\r\n# to the next number that has all its digits in increasing order from left to\r\n# right.\r\ndef nextNum(numList):\r\n # The list must have length greater than 0 for\r\n # this function to make any sense\r\n assert(len(numList) > 0)\r\n\r\n # Start with the least significant digit, and work towards\r\n # the bigger numbers\r\n index = len(numList) - 1\r\n\r\n # Increment the number\r\n numList[index] += 1\r\n\r\n # If this causes the number to equal 10, update accordingly\r\n while numList[index] == 10:\r\n # If the last spot in the number list is now at 10\r\n # that means there is nowehere left to increment, so\r\n # just terminate and return the messed up list\r\n if index == 0:\r\n break\r\n\r\n # Move the index to the left 1\r\n index -= 1\r\n\r\n # Demonstrate that ten 1's is equal to one 10 and add\r\n # accordingly.\r\n numList[index] += 1\r\n\r\n # Here's where things get weird. In the while loop above,\r\n # note that some indices of numList will have tens in them\r\n # here's where we make those numbers make sense. In the problem,\r\n # it's not necessary to loop through every number, we only need to\r\n # loop through distinct permutations of numbers with a certain number\r\n # of digits. e.g. if we just checked 123, we have also checked\r\n # 132, 231, 213, 312, 321. This loop ensures that we get a new DISTINCT\r\n # number that we haven't checked before. It makes everything much faster.\r\n for i in range(index, len(numList)):\r\n numList[i] = numList[index]\r\n\r\n return numList\r\n\r\n# This function takes a number in list form, and converts it to integer form\r\ndef listToNum(numList):\r\n # Start by taking the most significant digit\r\n num = numList[0]\r\n for i in range(1, len(numList)):\r\n # This ensures that the most significant digit ends up in the right\r\n # place.\r\n num *= 10\r\n\r\n # Add the proper digit in the proper spot\r\n num += numList[i]\r\n\r\n return num\r\n\r\n# This function takes a number in integer form and converts it to list form.\r\ndef numToList(num):\r\n # The easiest way to code this was to make the number a string...\r\n strNum = str(num)\r\n final = [0, 0, 0, 0, 0, 0]\r\n \r\n # ... then loop through the string and convert the character back to an\r\n # integer. I don't know if this is the most efficient way to do this,\r\n # but it was the solution that came to mind most quickly.\r\n for i in range(len(strNum)):\r\n final[len(final) - i - 1] = int(strNum[len(strNum) - i - 1])\r\n\r\n return final\r\n \r\n# This function sums the fifth power of the digits in an input number\r\ndef sumOfDigits(numList):\r\n final = 0\r\n for i in range(0, len(numList)):\r\n final += pow(numList[i], 5)\r\n\r\n return final\r\n\r\n# Run the program to determine the solution.\r\nif __name__ == "__main__":\r\n answer = problem30()\r\n print "Answer: " + str(answer)\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"