My workflow and macros:
Workflow:
Primes under N macro:
Truncatable Checker macro:
Answer: 748317
Last Week’s Favourite Solution:
Still struggling to download .yxdb files (only the .yxzps seems to work) however after reading through the solutions, @AncientPandaman solution has bee awarded last weeks favorite solution . With a 3 tool solution, winning the tool golf, this solution identified the redundancy of checking any even numbers, due to the trailing 0, when expressing them in base 2. Find their solution post on page one of last weeks solution or click here.
Mathematical Theory:
Project 37 posts a very similar challenge to Project 35, in the sense that the greatest gains can be made from optimizing the identification of primes. I decided to start by generating all the primes below 1,000,000 using the same technique as Project 35.
From there, it's a simple case of taking a prime number, then removing a digit from either side, and ensuring the value still appears in the prime number list.
An alternative method I did consider would be to construct the numbers in the first place. We know that (excluding the first/ left most digit) all digits must be a 1, 3, 7 or 9. The reason being that all digits will eventually end up in the “units” position. Excluding 2 and 5 themselves, any number ending in 2,4,5,6,8,0 is not prime as it is divisible by 2 and/or 5. Generating the input values in such a way would significantly reduce the number of values we need to check the primality for.
Method:
1) Generate all whole numbers from 2 to 999,999 using a generate rows tool. We start from 2 because it is the smallest prime number.
2) Pass this list into the Primes under n (improved) macro to identify all primes below one million. Inside the macro, we implement the sieve method discussed above, as follows:
a) The Summarize tool identifies the smallest remaining number in the list. This number must be prime, as it has survived elimination by all smaller primes (the macro only contains a small sample of dummy data).
b) A generate rows tool then creates all multiples of this prime, up to the maximum value.
c) A Join tool removes these multiples from the remaining list, leaving only numbers which are not divisible by the current prime.
d) Before looping back, a filter tool checks the exit condition. If the current prime is greater than the square root of the largest remaining value, the macro exits. All remaining numbers are confirmed as prime and are combined using a Union tool for output.
3) With the list of primes identified, a Formula tool is used to create a string copy of each prime number. Also, create two placeholder columns, which will be used to truncate the primes starting from both the right & left.
4) Feeding the data into the Truncatable checker macro.
a) To begin with, filter out the values which only have one digit remaining, as these can exit the loop.
b) Update the “Truncate” columns, by removing another value from the right / left.
c) Join both the right and left truncated values, to the full list of primes, to see if the truncated values are also prime.
d) Any values remaining can loop back round to be further trimmed/truncated.
5) With all the values output from the macro, filter out any which start as a single digit, like the question specifies.
6) The final step is to sum the truncatable primes output by the macro.
7) Submit your answer to the Project Euler Website!
Summary:
Like in Problem 35, an optimised approach, referred to as the prime sieve, was taken to detect prime numbers. This allowed for a large number of primes to be detected with minimal computation.
Want to find out more, follow this link to our introduction post – Euleryx: Let The Games Begin.
