My workflow: (SPOILER: Below is my workflow and answer, I'm loving the new community however am yet to discover how to insert a spoiler tag, so if you don't want to see the answer, scroll down a bit before reading on😄)
Workflow:
Answer: 40730
Last Week’s Favourite Solution:
I am fully aware that the last post was over a week ago but old habits die hard so this section's title will remain consistent! On that note, last week’s favourite solution award goes to @AncientPandaman. Instead of generating every possible two-digit fraction and then testing each one, they realised that by focusing on the structure of the cancellation itself, only four specific shapes of fraction needed to be considered. Using this knowledge, @AncientPandaman was then able to create only these fraction combinations , avoiding any which would be guaranteed to fail. Please find their solution on page one of last week’s post or click here.
Definitions:
- Factorial: The product of all positive integers up to and including a given number. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.
Mathematical Theory:
The key to solving this problem efficiently is identifying an upper bound for the input data. Already, this may be sounding familiar to some of you, as the same idea was used back in Project 30 (Digit Fifth Powers).
Without an upper bound, we could technically search an unlimited range of numbers, which is clearly not practical. In this case, the idea is to think about the extreme case where every digit is a 9, and see when the resulting sum can no longer keep up with the size of the number itself.
Since 9! (362,880) is the largest factorial of any single digit, the maximum possible sum of digit factorials for any given number occurs when every digit is a 9. This means, for any number of digits, the maximum sum is simply the digit count multiplied by 362,880.
Lets test this out with a few different digit counts:
- For a 7 digit number: 7 × 362,880 = 2,540,160, which itself has 7 digits, so this range is still possible.
- For an 8 digit number: 8 × 362,880 = 2,903,040, which only has 7 digits. This means no 8 digit number could ever equal the sum of the factorials of its digits.
This tells us that 7 digits is the maximum possible size for any valid number. More specifically, we only need to check numbers up to 2,540,160, giving us a clear upper bound for our input!
Method:
1) Input all whole numbers from 10 to 2,540,160 (our upper bound as found in the previous section). The problem excludes 1! and 2! and it should be clear that no other single-digit values could work, so we start from 10. Make sure to also, create a duplicate column containing the number stored as a string. This will allow us to parse out each digit individually.
2) Parse the digits out of the string, so each digit appears on its own row, linked back to its original starting number.
3) For each digit, calculate the factorial value, using the factorial function in the formula too, then sum the factorial values per original starting number.
4) Filter to only those records where the sum of the digit factorials equals the original number.
5) Sum the remaining values together to arrive at the final answer.
6) Submit your answer to the Project Euler Website!
Summary:
Finding a sensible upper bound was once again the key to this challenge. Without it, the input data could have been infinite. By considering the extreme case where all digits are 9, we were able to quickly narrow the search space down to a manageable size, making the rest of the workflow straightforward.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
