Euleryx Project 3 - Largest Prime Number

[Pilsner]

Welcome back to Project Euleryx, this time: Largest Prime Number.

This week's post is going to be a little longer than previous posts, as we'd like to cover some of the mathematical theory behind our solution. That being said, just because there is some theory behind our approach, doesn’t mean it is the only approach that works, so please feel free to share your thoughts below.  
 
 

Euleryx Problem 3 - Largest Prime Number

The challenge is to find the largest prime factor of the number 600851475143. 

 

Here's my full workflow and answer:

Spoiler

Workflow:


Macro:
 

 

Answer: 6857

Last Weeks Favourite Solution:
Another tough decision for our favourite solution so we have gone with a tie. Both @CoG and @gawa provided excellent solutions. Calculating the neccesary terms only and storing variables within a single column in a generate rows was genius. Checkout there solutions on page one of last weeks challenge 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: 
 

  

During this problem, we exploited what’s called the Fundamental Theorem of Arithmetic (FTA), which states: 
 

“Every positive integer (whole number) can be written as a product of prime numbers, or the number itself is prime.” 

e.g.  
If we take the number 30, we can write this as 2 x 3 x 5 

The Method to our Madness (Factor Trees): 

We decided that to tackle this problem, we would list all the prime factors of the number, then simply take the largest. The tricky part here was creating that list of prime numbers.  

 

Using the Fundamental Theorem of Arithmetic, we know that 600851475143, can be written as a product of its prime factors. But how do we find these prime factors? We decided to use what's called a factor tree. 

A factor tree works as follows: 
 
1) Identify any 2 factors of your number. 

2) If the number is prime, circle it. 

3) If the number is not prime, thanks to the FTA, we know that it too can be expressed as a product of its primes, so, repeat steps 1 and 2 for each uncircled number. 

4) Stop when there are no more uncircled numbers at the bottom of the tree.  

e.g. for the number 30, the tree would grow as follows: 

First step: 

Second step: 

 

Therefore for we can see, 30 can be written as 5 x 2 x 3 

In case you’re worried that you didn’t think of 5 and 6 to begin with, rest assured, it doesn’t matter which two numbers you choose, as long as they make up a factor pair. Here are some other examples of possible factor trees for the number 30: 

 

All of which lead to the same answer. With this in mind, the only thing left was to create a workflow in Alteryx, that can create these factor trees.  

Setting up the Workflow: 

 

Whilst all this theory is great, we still need a way to get the computer to do the hard part. If it wasn’t apparent from the above, we will be using an iterative macro to solve this problem. So, the first step is to decide what information we need to be passed between each iteration.  
 
For this question, we fed 3 columns into the macro, as shown in the image below. You will notice we have two starting numbers to help illustrate the workflows process, as we step through it: 

 

The Iterative Macro: 

  

Yes, it's time for the tough part, but fear not, let's break the steps down together. On each iteration, our goal is: 
 

• To find one prime factor 

• Add this to the “List of Prime Factors” Column 

• Update the number field to be the factor pair of the identified prime number.  
  
  

i.e. at the start of the first iteration: 

 

vs the end of the first iteration (on the loop anchor). Notice [Number] * [List of Prime Factors] = [Starting Number] 

This is achieved as follows: 

Spoiler

1.  Use a generate rows to create a list of numbers until it reaches an integer factor. (This only works for odd numbers > 1, we deal with the others soon.) The integer it stops on will be the Lowest prime factor of the value in the “Number column”. 
   
   Before generate rows: 
   
   
   After generate rows:
    
   
    
2. Using the Summarise tool, find the maximum value in the list for each “Number”, as this is the lowest prime factor.  (Note: We take the maximum value as the generate rows stopped once it found the first prime factor, hence all smaller values are not factors).
    

    

   
   
   
3. Now we deal with the remaining values (even numbers or the number 1)  
   Here we check if a number is even or not: 
   
   
   1. If it is even, then set the lowest Multiple = 2. 
   2. Otherwise, filter the value out of the loop, and towards the macro output. 
      
      
      
      
4. Union all the records with prime factors, back together and update the List of Prime Numbers column:
   

    

5. Filter out any rows where the Lowest Factor = the Number column, as this means all prime factors of the starting value have been found. Output these rows of data from the macro.
   
   For records still in the loop, we must update the three original columns ready for the second iteration. 
   
   
   
6. Update the number column by doing the [Number] / [Lowest Factor]. (This step effectively creates the other branch of your factor tree.)  
   
   

    

   Without this step, each iteration would be passing the same number through, so it's vital that we remember this part.  
   

    

   
   
   
   
7. Drop any columns created during that iteration and feed the results into the loop output.
   

    

   
    
8. Relax as the iterative macro is complete: 
   

    

   
   
   

Final Steps: 

Running this macro should give you the following output.  

As you can see, all the prime factors are listed in the “List of Prime Factors” column, with a comma separating them. It's important to note that this list may include duplicates, for example, if you started with the number 4, the “List of all prime Factors” should be “2,2” as 2 x 2 = 4. 

 

To find the largest prime factor for each starting value, simply parse out the “List of Prime Factors” columns, sort the results descending, and select the top record per “Starting Number”: 

 

Now, all that's left to do is submit your answer to the Project Euler website! 

Summary: 

By using Alteryx to Iteratively create a factor tree, one branch at a time, we have been able to reduce any number down to its prime factors. Thanks to the Fundamental Theorem of Arithmetic, we know that the largest prime number from our list, is indeed the largest prime factor of 600851475143. 

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

[Qiu]

I used the macro from here to speed up the Prime Number finding process.
https://community.alteryx.com/t5/Weekly-Challenges/Challenge-187-Generate-Prime-Numbers/m-p/482140/h...

Spoiler

[AkimasaKajitani]

My solution.

Spoiler

1. Because the number of targets is large, I created only odd factor candidates up to the square root of the target number.
2. I kept only those that were evenly divisible (this narrowed the target to 8 records).
3. I set the Generate Row tool to stopping calculating each factor candidate once it was evenly divisible.
4. I filtered for those where the result of the row generator + 1 is the original factor candidate.
5. The largest one is the correct answer.

[patrick_digan]

Spoiler

I generated all of the possible factors <=the square root to get 775,145 numbers to check. Only 7 are factors. Instead of checking which of them are prime, I just checked which of the factors do not have a smaller factor by which it's divisible. After cartesian joining the 7 factors, only 4 made through and the largest was 6,857.
 

[DaisukeTsuchiya]

This is an interesting challenge.

Spoiler

First, I determined the prime numbers up to 10,000. The number 10,000 was chosen arbitrarily. Finding prime numbers itself was easy because I had done it before in a Weekly Challenge.

After appending the obtained prime numbers to the original number, I used the Mod function to filter out prime factors. Then, I multiplied these to confirm that they matched the original number, ensuring the prime factorization was correct.

However, this approach is incomplete if the same prime number appears multiple times or if there are prime factors larger than the initially assumed maximum prime factor. Therefore, I also created a macro to perform complete prime factorization. This involved continuously dividing the original number by the prime factors until it reduced to 1.

For this problem, since we only need to find the largest prime factor, we can get the answer through a few rounds of Try & Error without using a macro.

[TheOC]

Fun challenge!
After having a look through, I think my solution is most similar to @caltang's. Great minds think alike 

Spoiler

Generate all numbers up to the sqrt of the number, then use the mod function to remove any (to get all factors).
I did a separate filter to remove all even factors first - figured this would speed things up as the number we're checking is odd.

Then effectively did that manual check again against all factors - to check if they're prime.

Shout out to @Carolyn for adapting a prime number checker macro - great way to make the process reusable.
@CoG's solution goes straight over my head... for now. Very impressed you can cram so much logic inside a single generate rows.

Thanks for the knowledge share, all!

[martinson]

I FINALLY GOT IT!

Spoiler

Time: Like 2 days