Euleryx Problem 30 – Digit Fifth Powers
My workflow:
Spoiler
Workflow:
Answer: 443839
Last Week's Favourite Solution:
Last weeks project saw several streamlined methods of handling large number powers, however the solution awarded last weeks favourite solution was, @AncientPandaman's solution which looked at identifying values head of time buy simply rearranging formulas / spotting patterns. For example, every even power of two, is also a power of four, so we know these only need to be counted once. After creating a table which accounted for all of these patterns, @AncientPandaman was able to create a macro less solution, without even having to compute any of the powers. Please find their solution on page one of last week's post or click here.
Mathematical Theory:
When I first read this project, I thought the question was wrong. It asks us to find ALL values that can be expressed as a sum of fifth powers of their digits. I was thinking, it can't be expecting us to test values up to infinity.
Then, after a little thinking and some minor frustration at the question, I realised a trick. It goes as follows:
If the number had six digits, then what is the greatest possible sum of fifth powers (for the digits)? Well, as we are dealing with powers of single-digit numbers, 9^5 = 59,049, is the largest value for any single digit. Therefore, considering the maximum possible sum for a 6-digit number, we would need to consider the number 999,999.
Taking the 5th power of all of these digits, then summing them is as simple as:
6 x 59,049 = 354,294
Which, although it doesn’t equal our starting value, does at least yield a six-digit number. However, if we try the same trick with seven-digit numbers, it’s a different story.
Lets considering the 7-digit number 9,999,999 (the largest possible fifth power, digits sum). If we put all of its digits to the power of 5, and then sum them, we get:
7 x 59,049 = 413,343
But this is only a 6-digit number. 9,999,999, yields the largest possible value for the sum of its digits' fifth powers. As its sum is less than 7 digits, we can conclude that no 7-digit number will ever be a solution to this problem. In fact, the largest possible solution for the problem, must be at most 6 digits long.
Now that we know six-digit numbers are the largest possible solution, we can restrict the problem further. As previously calculated, the maximum possible sum of fifth power digits, for a 6-digit number is:
6 x 59,049 = 354,294
This means that there is no possible solution where the value is greater than 354,294. With this knowledge, we can now use this value as an upper bound for the problem, meaning that instead of trying to consider numbers up to infinity, we only need to consider those between 2 – 354,294.
Method:
1) As always, the first step is to generate our input data. As discussed above, we know that the maximum possible number that would equal the sum of its digits’ 5th powers would be 354,294. Therefore, we can use a Generate rows tool from 2 – 354,294 to produce our input.
2) After creating a copy of the initial column (this time stored as a string), we can then parse the digits, so that there is a single digit per row.
3) With the digits isolated on separate rows, we can find the 5th power for each and every digit.
4) Once the powers have been calculated, the next step is to sum all of these powers (per starting number), to calculate the “sum of the fifth powers of their digits”.
5) The final steps are nice and simple: filter the data to records where the Sum of the powers = the starting number, then sum these remaining values.
6) Submit your answer to the Project Euler Website!
Summary:
Despite an initially daunting task, this problem was another bounding challenge. By considering the feasible solutions and identifying a maximum possible value, we were able to then deploy some simple “brute force” style tests to check all the values within our range.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
