Euleryx Problem 32 – Pandigital Products
My workflow:
Spoiler
Workflow:
Answer: 45228
Last Week's Favourite Solution:
Last week several solutions used a technique called Dynamic Programming. This technique requires minimal computation as it is able to efficiently calculate the number of possible combinations for a given value, but using the number of possible combos for the previous coin (when sorted in ascending order). @Qiu submitted the first solution utilising this technique and therefore wins last weeks favourite solution. Please find their solution on page one of last week's post or click here.
Definitions:
- Multiplicand: The number being multiplied in a multiplication (on the left of the x symbol)
- Multiplier: The number multiplying the multiplicand (on the right of the x symbol)
- Pandigital: Contains all the digits, exactly once, based on the defined range of digits.
Mathematical Theory:
My solution to this weeks challenge is again more from the bruit force angle so I'm looking forward to seeing some of the solutions from others! That being said, I have still tried to identify only the relevant records to compute/test.
The first issue with this weeks problem, for me anyway, was understanding it.
What I eventually figured out is that it is effectively looking for a multiplication equation, which has exactly 9 digits involved, all of which are distinct and take a value 1-9 (i.e not 0). So the equation 39 x 186 = 7254 works, as it is a correct calculation, and the number 391867254 is 1-9 pandigital.
After digesting the equation, the next step is to consider the possible equations. As we know the whole equation needs 9 digits, lets only consider cases which can possibly yield such an answer.
i.e a two digit number multiplied by a 3 digit number, CAN equal a 4 digit number. The total number of digits is then 9 meaning it might satisfy the conditions as per the problem. However, a 2 digit number multiplied by a 4 digit number will always yield at least a 5 digit number. This makes a total of 11 digits, meaning that this setup will never provide a solution to the problem at hand.
The easiest way to figure out the valid combinations is just to consider the possibilities. You can calculate the extremes, i.e for a one and three digit number:
- Min: 1 x 100 = 111 (7 digits)
- Max: 9 x 999 = 8991 (8 digits)
Both under 9 digits therefore one digit x three digits wont work. Or mentally test a value or two until you have verified the combination status. Either way you should conclude that the only possible combinations are:
- Two digit numbers x three digit numbers
- One digit numbers x four digit numbers.
With this in mind you can then generate all possible combinations, calculate the product, and then verify the presence of 9 distinct (non 0) digits.
Method:
1) The first step was to generate all values up to and including 4 digit values. Knowing that a digit cannot be repeated, the maximum can be set to 9876 and any values higher than this repeat at least one digit.
2) Next, the numbers were separated based on their number of digits and then appended back to form all the combos of 1 & 4 and 2 & 3 digit numbers.
3) Preform the multiplication to complete the equation. It is also useful to create a column which concatenates all the digits together.
4) Use the regex tool to parse the “All digits” column to contain a single digit per row.
5) For each calculation, count the number of distinct and total digits in the all digits column.
6) All that’s left to do is filter down the table to only include those with 9 total and distinct digits (and make sure they don’t contain a zero), then deduplicate and sum these remaining records.
7) Submit your answer to the Project Euler Website!
Summary:
Considering numbers purely in terms of their number of digits enabled us to quickly identify the values worth testing. From here the problem was relatively simple as we could perform the multiplication then validate the equations based on the question criteria.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
