Euleryx Project 7 - 10 001st Prime

[pilsworth-bulien-com]

Euleryx Problem 7 - 10 001st Prime

Last Weeks Favourite Solution:
Last week @gawa spotted that if we simply rearrange the equation, we can cancel out some like terms, avoiding the need to do any form of subtraction. We thought this was a great approach, and therefore, it gets our favourite solution award! Find it on page one of last weeks 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.

My workflow and macro:

Spoiler

Workflow:

Macro:

Answer: 104743

Mathematical Theory:

As we know, a prime number has only two factors. That means, if we take all numbers less than our prime value (and greater than 1), none of them will have a multiple of our prime value. To help clarify what I mean, let's take the number 5 as an example.

The list of numbers less than 5 (and greater than one) would be: 2, 3 and 4.

The first few multiples of these numbers would be:

2: 2, 4, 6, 8, 10, 12

3: 3, 6, 9, 12, 15, 18

4: 4, 8, 12

As you can see, there is no 5. Excluding 1 and 5, all other numbers are greater than 5, therefore can't be factors of 5. This means 5 must be prime.

Now, how do we find the next prime number? Well, let's find the first few multiples of 5

5: 5, 10, 15

Looking at the list of multiples, 6 has already been included, so we know that not prime. We can still find its first few multiples, though.

6: 6, 12, 18

The number 7 has not appeared in any of the lists of multiples; therefore, it must be prime.

Those with keen eyes may have spotted some redundancy too, all the multiples of 4 and 6 are also multiples of other (prime) numbers. In fact, this is true of any non-prime because a factor will have all the same multiples, and more multiples, than the original number. Thanks to the Fundamental Theorem of Arithmetic (as explained in Problem 3), we know that any non-prime, can be expressed as a product of its prime factors (therefore has factors which are prime). 

If we were to generalise what we are doing above, we are simply listing multiples, identifying numbers which haven’t appeared. Now let's flip the script and instead of building up a bank, let's reduce an existing list. I.e let's find all the prime numbers from 2-10. We’ll, start with a list of numbers 2, 3, 4, 5, 6, 7, 8, 9, 10.

• Select the smallest number in the list, in this case 2, which is prime.
• Find all the multiples of 2, under (or equal to) 10. They are 2, 4, 6, 8, 10
• Remove these from our original list to get, 3, 5, 7, 9.
• Again, select the smallest number (3), which must be prime as its not a multiple of any of the numbers smaller than it. If it was, it would no longer be in the list.
• Find all multiples of 3 under 10. They are 3, 6, 9
• Remove these from the list. 5, 7
• Take the smallest number (5)
• List all multiples under 10. They are: 5, 10
• Remove these from the list to leave 7
• With just one number remaining, we know it must also be prime. Therefore, the prime numbers under 10 are 2, 3, 5 and 7.

This idea can be extrapolated out over a much larger range, and that is the basic idea I used to tackle this particular Problem.


Method:

In order to use the method above, we do need to choose the starting list size. Admittedly, this is a potential downside to this method; however, I believe the quick run time counteracts this. As we are looking for the 10,001^st prime, I decided a starting list of 200,000 should be plenty big enough.

1. Generate your input data:
   
    
   
2. Implement the three-step process covered above via an iterative macro:
   
   - Take the smallest number from the list
   
   
   
   - Find all its multiples:
   
   
   - Remove these multiples from the main list using the join tool:
   
   
   - Using the Engine iteration number, check to see if we are at the 10,001 prime number yet. If not, feed the remaining numbers into the looped macro output.
   
   
   
3. Sort the list and sample the last value to isolate the 10,001^st prime number
   
   
4. Submit your answer to the Project Euler Website!
   
   

Summary:

By taking a different approach to previous weeks and actually, starting with a full dataset and then reducing its size down each iteration, we were able to find the 10,001^st prime number.

Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.

[pilsworth-bulien-com]

I didn't know there was an equation for bounding prime numbers. I feel like that will be handy to know for the future challenges.