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.

[DaisukeTsuchiya]

The problem of finding prime numbers will often appear in Project Euler, so I share a macro that speeds up the process. 

Spoiler

Prime numbers can be calculated within 10 seconds for up to 1 million, 1.5 minutes for up to 10 million, and even within 30 minutes for up to 100 million by this macro. However, for this problem, calculating up to 110,000 is sufficient, so even brute force methods are adequate.

[AkimasaKajitani]

My solution!

My 1st workflow took over 2 minutes, so I remake my workflow and now it takes 0.8 seconds.

Spoiler

The Generate Row tool does not output a result when the condition is met. For the trial division, I wanted to know whether I had divided it down to SQRT(N), so I needed to devise a way to find out whether I had divided it down to SQRT(N) or whether it was evenly divisible.

I made a judgment first within the LoopExpression, and if the condition was met, I output a value as a flag(-1) to prevent the loop from ending, and then exit the loop in the next loop.

[Yoshiro_Fujimori]

My solution.

Spoiler

Workflow

Macro

[Carolyn]

Team brute force

I generated a list of 2 and then all odd numbers (e.g. 2 - 3 - 5 - 7 - 9, etc). Then I used my Prime Macro to determine which was prime and found the 10,001th value.

I'm looking forward to see the w*tchcraft [which is apparently a banned word... who knew] that other people used to do this more efficiently :)

Spoiler

[pilsworth-bulien-com]

There really are so many ways to find prime numbers, loving the fact that everyone's solution is different so far. 

@DaisukeTsuchiya , your absolutely right, prime numbers seem to be a common theme in Project Euler, thank you for sharing the macro.

Just thought I'd share one more method for solving this one:

Last week @gawa posted a custom formula function here, specifically designed for checking the primality of a number. I used this to solve this Euleryx challenge:

Spoiler

1) Generate 1,000,000 million rows (this is very overkill, but I wanted to really test the function's speed).
2) Filter using the new custom function: 

3) Order the results and Record ID them.
4) Filter to the 10,001st number

I was obviously expecting the function to work but I was still quite shocked by its speed. In just 0.5 seconds, the entire workflow had ran (there were 1 million records)!

Would highly recommend checking this custom formula out if you haven't already

[Qiu]

It takes 17 seconds for me.

Spoiler

I use the macro from here.

https://community.alteryx.com/t5/Weekly-Challenges/Challenge-187-Generate-Prime-Numbers/m-p/482140/h...

[gawa]

Thank you for mentioning my post @pilsworth-bulien-com !
I know that the  custom formula technically violate the Base-A rules. However, problems themed around prime numbers frequently appear in Euleryx. Repeating a time-consuming process each time with Macro can detract from the essence of the problems. I would encourage all to utilize IsPrime function so that they can enjoy the challenges more!

[pilsworth-bulien-com]

@gawa, that's a very good point about the essence of the problem. I think we've all proven we can check the primality of a number using 100% Base-A, so I don't see any harm in using your function going forward, especially considering its impressive speed😄

[CoG]

String coding continued although the workflow isn't quite as efficient

Spoiler

Key useful fact is that the n-th prime p_n < n * ( ln(n) + ln(ln(n)) ). That, combined with an optimized version of my factor finding, Generate Rows Tool allows us to find all primes from 1 to the upper bound and then isolate the 10001-th:

Happy Solving, everyone!