Workflow:
9 digit multiples:
Answer: 932718654
Last Week’s Favourite Solution:
Another tough call but (for the 3rd week in a row!), last weeks favourite solution is awarded to @AncientPandaman. While most approached started with a list then whittled it down to the final set of values, @AncientPandaman began with just the 4 unit prime numbers, then constructed a minimal list of candidates, which had already been validated for the left to right truncation. From there all that remained was to test the primality when truncating values from the other direction. Find their solution post on page one of last weeks solution or click here.
Note: The next post will launch on Thursday 28th, due to Inspire being held next week! I look forward to seeing you there!
Mathematical Theory:
Pandigital values are once again the focus of a Project Euler question. This time, the numbers are created by concatenating consecutive multiples of smaller value, one example being 327.
327 x 1 = 327
327 x 2 = 654
327 x 3 = 981
Which all together yields 327654981.
However, the challenge is to calculate all the possible values, inorder to find the greatest. If we were to test all numbers up to an including 9 digit value, the required computation would be huge. Fortunatly, hidden within the problem itself is a key to minimising the ask.
The question specifies than n > 1. This means, we must concatenate a minimum of two digits (1 and 2 times the starting value). We also know, that both (or all) the multiples, must have a total of 9 digits.
Combining these two facts, we know that the minimum starting number is a 4 digit number. This becomes obvious when we consider the case of a 5 digit number, the smallest of which being 10,000.
10,000 x 1 = 10,000
10,000 x 2 = 20,000
Concatenating these values gives, 1000020000. With 10 digits this value violates the conditions of the question therefore 5 digit starting values do not need to be considered.
The other slight improvement builds upon the fact we are starting with 4 digit value. As explained in Project 32, the fact we are looking for a pandigital answer allows us to reduce the maximum value to 9876.
Method:
1) Generate records from 1-9876, and create a second “copy” column, stored as a string. Any starting number with over 4 digits, would lead to a minimum of 10 digits, when concatenating the multiples, hence we don't need to consider such records.
2) Input the records to the 9 digit multiples, iterative macro.
a) Inside the macro, the first main step involves updating the “full value”. This is done by calculating the next multiple of the starting value, then appending it to values already in this concatenated column.
b) With the updated concatinated values, in the “Full Number” column, filter first to records which are 9 digits long exactly (these can be removed from the loop and output from the macro). Then separate the remaining values into those above or below 9 digits. Any below can be looped again, whilst those above will be dropped.
3) After the macro, the remaining values are all 9 digits long. These values then need to be check to see if they are pandigital. To do this, the digits are first parsed to one per row.
4) Count the number of distinct digits per number.
5) Filter to numbers which have 9 distinct digits (and none of them are 0, as by definition these are not pandigital).
6) Finally, sort the 9 digit numbers in descending order then sample the top records to identify the greatest value.
7) Submit your answer to the Project Euler Website!
Summary:
Acting as a great reminder of "the devil is in the detail", the efficiencies of this project could be unlocked by ruling out start values, which yield impossible solution. After identifying such information, the project became a relatively simple adaptation from project 32.
Want to find out more, follow this link to our introduction post – Euleryx: Let The Games Begin.
