Euleryx Project 10 – Summation of Primes

[pilsworth-bulien-com]

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,001^st 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:

1. We already know that all multiples of previously identified prime numbers have been removed.
2. This means that the only way a number is NOT prime, is in the case where one of the remaining numbers is a factor.
3. 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:

1. Take the smallest number from the list
   
   
   
2. Filter the list to get all numbers, less than double this minimum value:
   
   
3. Generate all multiples of the extracted prime numbers, under 2,000,000.
   
   
   
   
4. Remove these multiples from the main list using the join tool:
   
   
   
   

3) Sum all the values from the list:

• Submit your answer to the Project Euler Website!
  
  
  

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.

[Qiu]

@pilsworth-bulien-com 
Thank you for the new challenge.

Spoiler

I simply copied the macro from this thread. by @danilang and made some opitimization of data before entering the macro.
I will check yours and try to make mine faster. 😁

[DaisukeTsuchiya]

I use the macro to calculate Prime Numbers for question 7. The processing time is 14 seconds.

Spoiler

[CoG]

Nice macro approach! I like the optimization. My goals are to avoid macros and thus my solution is less efficient, but string coding continues!

Spoiler

Problem 7 is definitely the go to. All I did is change the logic to look for primes under 2M. Nothing Special (The next problem (#11) has a crazy solution though)


Not sure how your macro would handle it, @pilsworth-bulien-com, but you can technically take every remaining value < square of the remaining minimum.

Happy Solving, y'all!

[AkimasaKajitani]

My solution!

I reuse the Problem 7 Prime Number generator.

Spoiler

[gawa]

Two different approach

(Non-Base-A) Use IsPrime() custom function => 0.7 sec

(Base-A) Generate Rows tool approach instead of Macro =>20 sec

Spoiler

As the prime number is always 6N+/-1 except for 2 and 3, we can reduce the numbers to be examined whichever going with Macro or Generate Rows.

6N => divisible by 6
6N+/- 1 => not divisible by either of 2 and 3 that can be the prime number
6N+/- 2 => divisible by 2
6N+/- 3 => divisible by 3
6N+/- 4 => identical to 6N+/- 2, that is divisible by 2
6N+/- 5 => identical to 6N+/- 1