My workflow and macros: (While I can now insert spoiler tags, like others, Im having issues when trying to put an image in the spoiler, so please skip the below section, if you want to avoid the answer).
Workflow:
Primes under N macro:
Circular Primes macro:
Answer: 55
Last Week’s Favourite Solution:
This week, the winner of last week's favourite solution is slightly different. Unfortunately, I cannot seem to download the solutions yet on the new community, so it made looking into answers quite challenging. So – instead of a winner for the best solution to Problem 34, last week's favourite solution goes to @AkimasaKajitani , for sharing how to insert a spoiler tag on the new community. If you want to learn how or do this you can find @AkimasaKajitani post on page one of last weeks solution or click here. I look forward to stepping through the solutions in more detail, once I can download them!
Definitions:
- Circular Prime: A prime number which remains prime through all cyclic rotations of its digits. For example, 197 is a circular prime because 197, 971 and 719 are all prime.
Mathematical Theory:
The main challenge with this problem is efficiency. We need to identify every prime number below one million, which means we need a fast way to sieve through a large set of numbers. The quickest way to achieve this is almost certainly through the use of @Gawa's IsPrime custom function (found here). However this week, I decided to try and improve upon a macro I created previously, to help with this same problem. I found out retrospectively that the method I have used can be referred to as the Sieve of Eratosthenes.
The sieve works by starting with a full list of numbers and removing multiples of each prime. Each time you do this, the smallest remaining number will then be your next prime, due to the fact it has survived elimination by all smaller primes. This process then simply repeats. As an example, lets try and find all primes up to 29:
3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29
The smallest remaining number after 2 is 3, which again must be prime. Removing the multiples of 3, leaves
5, 7, 11, 13, 17, 19, 23, 25, 29.
Doing the same with 5, we get
7, 11, 13, 17, 19, 23, 29.
And through repeating this we will eventually rule out all values. Taking each of the numbers we identified as prime, in each iteration, we are left with
2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
This method was explored in more detail back in Problem 7. While this method still works, there is a key optimisation which will massively reduce the number of iterations required. The square root of 29 is approximately 5.39, and 7 is greater than that, so after extracting out the 5, we could actually stop the process there as every number still in the list is guaranteed to be prime.
The reason this works comes down to factor pairs. Taking 36 as an example. The square root for 36 is 6. This means 6 x 6 = 36. But what if I increase one of the “6s” slightly.
6.4 x 5.624 = 36
By increasing one of the values, the other one has to decrease to ensure the equation still balances. This means that unless a factor equals the square root, all factor pairs, have one factor above, and one factor below the square root.
Going back to the optimisation example from above. Once we get to 7, (which is greater than the square root of 29 ~ 5.39), we know that all prime values less than the square root of 29 have already been found. If any of the remaining numbers had a factor pair producing a value under 29, the smaller factor would be below the square root, and we would have already removed it during an earlier iteration. Since none of them were removed, there is no factor pair which will equal these values, and therefore, all remaining values must be prime.
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. This will allow the next section to easily reorder the digits, to validate the circular prime criteria.
4) Pass the primes and their string copies into the Circular Values within list macro. This macro checks whether each rotation of a primes digits, appear in the list of primes:
a) Firstly a filter tool checks whether the number of digits in the string equals the current iteration number plus one. If it does, the value has been fully rotated and is output as a confirmed circular prime.
b) For the remaining primes, a Formula tool uses regex, to rotate the digits by one position (moving the first digit to the end of the string).
c) Joining back to the input data we can validate if the rotated version is indeed also a prime, filtering out those which don’t join.
5) The final step is to count the number of circular primes output by the macro.
6) Submit your answer to the Project Euler Website!
Summary:
The biggest trick used in this problem is the square root optimisation within the “prime sieve”. Without it, the iterative macro would need to cycle through every prime below one million, which would be extremely slow. By recognising that all, non-prime numbers must have a factor less than or equal to their square root, and were therefore already removed, we were able to exit the sieve far earlier.
Want to find out more, follow this link to our introduction post – Euleryx: Let The Games Begin.
