Overview

The third Euler Project Problem asks you to decompose a large integer to find its largest prime factor. Sounds simple enough. However, it took me four days and twice as many hours going through multiple tacks before I finally got an answer. Unfortunately, it doesn’t feel like a win though, because I wound up having to execute someone else’s Python code. I converted it from Python 2.7 to 3.6 using this tool. I then saved it as a local Python script and ran it using the Anaconda IDE, obtaining an answer within less than half a second.

That answer allowed me to open the forum to see other options and the official pseudocode which I converted to an R script and ran within 0.24 seconds. Annoyingly fast compared to the things I tried that failed.

Stuff that Didn’t Work

The first thing I tried was to create a while loop of all integer divisor answers. I then removed answers that weren’t prime. This was both inefficient, and it didn’t work. I kept running into issues with it removing prime answers in the test sequences I ran. I tried running this Monday morning and after 11 minutes was less than 0.00009% of the way through.

My next strategy was to try to create a list of primes to divide the test number by to see if it gave my answer. The pre-made lists I found weren’t formatted correctly to use as a list in R and I didn’t want to spend the time needed to clean them up. I tried using the primes package to generate a list up to the number I was checking. The package was unable to calculate primes large enough for that attempt. It was a few orders of magnitude short.

I tried again with the same concept of dividing by primes, this time using for loops. However, those loops were not calculating. I’m not certain whether I simply missed a character or two in writing the loops, or if they were flawed from the beginning. Regardless, they didn’t work.

Explaining What Did Work

In the intro, I linked to someone’s Python code which finally got me an answer. I also converted the official pseudocode to my answer, which you can see here. The pseudocode converted to R works in the following manner:

Start with the number being examined (N). Start an if loop checking to see if if the modulo of N/2 is equal to zero. If that is true, store N as N/2. Update a working variable of the last working factor to equal 2. While the modulo of N/2 is still equal to 2, continue updating N with N/2.

If the modulo of N/2 is not equal to zero, the working variable of the last working factor is now equal to 1.

Moving on, update a different working factor to 3.

While N is greater than one, if the modulo of N divided by this new factor (factor) is equal to zero, update N to become N/factor. Update the last working factor to equal factor. While the modulo of N divided by this factor is equal to zero, update N to become N/factor [this one seems a bit superfluous, but it works, so I kept it].

Update factor to be factor + two (so you’re skipping non-prime numbers).

Once the full loop is complete, display the last working factor value.

Lessons Learned

In struggling with this problem for several days, I found that there are clearly multiple possible paths to the answer. The most optimal one may not be the first path that shows up. I learned about the groundhog package to help maintain reproducibility, though I’m still learning on that one as well. I also learned that some of these can take a while to figure out.

I plotted one of the working lists to see if it followed a discernable pattern, which I will likely continue in later problems. The short answer is yes, it does follow a pattern. The long answer is, eh, the pattern isn’t particularly useful. More work would need to be done to pull something useful out of it.

For future stumpers, I’ll be posting my progress on Twitter each day I work on it. I’ll create partial posts each following Sunday if I’m still working on it.