Euleryx Problem 10 – Summation of Primes
Spoiler
My workflow and macro:
Macro:
Answer: 142913828922
Last Week's Favourite Solution:
It's been a while since I've got quite this stuck in the weeds with some algebra, but dare I say it, it was good fun. @CoG managed to derive some equations, allowing us to represent both a, and c, just in terms of b. Pairing that with the triangle rule (shout out to @Yoshiro_Fujimori for spotting this first), @CoG , was able to get a solution by generating just 206 rows of data, making it out favourite solution from last week. Find it on page one of last week's post, or click here.
Definitions:
- Factor: A number that divides another number exactly (i.e no remainder or decimal)
- Prime Numbers: A number with exactly two unique factors: 1 and itself.
Mathematical Theory:
This week, we are going to revisit some of the work carried out in Project 7. In Project 7 we looked at finding the 10,001st prime number. The way I approached this was to start with a list of numbers, then filter out certain values, until we were left with prime numbers. This was achieved by creating a list of numbers, then each time taking the minimum value from that list, as it was guaranteed to be prime. Any multiples of that minimum value would then be filtered out, too, and the process would repeat. If you want the full explanation, please look back at Project 7, as this week will be building upon the same logic.
So, assuming we have a set of numbers (starting at 2, and increasing by 1 each step), we already have a macro, which can check the primality of the numbers in this list. If the list were from 2-12, the iterations would go as follows:
Iteration | Input | Prime Identified |
1 | 2,3,4,5,6,7,8,9,10,11,12 | 2 |
2 | 3,5,7,9,11 | 3 |
3 | 5,7,11 | 5 |
4 | 7,11 | 7 |
5 | 11 | 11 |
However, when 2 million records were fed into this macro, it was quite slow, hence we had to get creative. The trick here involves identifying more than one prime number in each iteration. Instead of just selecting the minimum value in the list, we can actually select all values which are less than double the minimum.
This works because of the following:
- We already know that all multiples of previously identified prime numbers have been removed.
- This means that the only way a number is NOT prime, is in the case where one of the remaining numbers is a factor.
- All numbers under half the minimum value cannot be multiples of any other number, as the smallest multiple possible is a multiple of 2.
Taking the same example as before:
Iteration | Input | Primes Identified |
1 | 2,3,4,5,6,7,8,9,10,11,12 | 2,3 (as both are less than 2x2 = 4) |
2 | 5,7,11 | 5,7 (as both are less than 5x2 = 10) |
3 | 11 | 11 |
With just 12 records, we've reduced the number of iterations from 5 to 3. As we deal with larger numbers/sequences, the time saving will only increase.
Method:
In order to use the method above, similarly to before, we need to generate our input data.
1) Generate your input data:
2) Implement the revised four-step process covered both above and in problem 7:
- Take the smallest number from the list
- Filter the list to get all numbers, less than double this minimum value:
- Generate all multiples of the extracted prime numbers, under 2,000,000.
- Remove these multiples from the main list using the join tool:
3) Sum all the values from the list:
Summary:
By making one simple adjustment to a previous macro, we have been able to reduce the processing time on a list of prime numbers for several minutes, down to under 3 seconds! I believe this method could still be significantly improved upon, keen to see if anyone spots any other tricks.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
