Euler Project: Challenge #3

Ok, so a while back (I don’t remember exactly when). I tried to get into the Euler Project. What it is is a series of difficult mathematical (programming) challenges. When I first tried it, I solved the first two challenges, and couldn’t progress much further.

Anyway, I was recently on a bit of a programming spree, and gave challenge #3 another shot. Instead of coding my solution in Javascript, I have now switched to Python (a newer, lower level, yet more elegant, programming language). This post is an explanation of how I solved it, so if you don’t want the solution spoiled, go and figure it out yourself (then please come back here to tell me how inefficient mine is).

The exact problem, as stated on the website, is:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

As you can see, it is quite a nicely stated problem since it gives you a number you can test out before trying to compute the highest prime of the monster 12-digit number. Initially, I went about coding my solution in a fairly obvious way (pseudo code)

loop bigNumber:

  if number%bigNumber == 0 (i.e. if there is no remainder, then it’s a factor) then
   loop through factor to check if it has factors. if it has none, then it’s prime!

Now, this logic worked fine for the relatively small 13195 (in 0.011 seconds, I might add) but when I threw the huge number at it, the program just hung (sat there, showing no result). After examining it in more detail, I found that it was simply going to take too many life times to check all the factors.

However, I knew there must be a solution that didn’t involve a supercomputer, since I know a guy who solved this problem. Back to the drawing board…

My basic problem was one of efficiency. So in my second version of the program, I changed the program in two different ways. I manually multiplied the number (also known as chunking, a mistake in hindsight, since the computational equivalent of long-division is, in fact, faster). The second change I made was a bit more complicated, but I personally found it fascinating. So, please humour me for a moment with this explanation:


Let’s find out if 13 is a prime number.
So we’ll check the potential factors one by one:

  1. 2 times 2 is 4
  2. 2 times 3 is 6
  3. 2 times 4 is 8
  4. 2 times 5 is 10
  5. 2 times 6 is 12
  6. 2 times 7 is 14 (greater than 13, so we’ll jump to the next number)
  7. 3 times 2 is 6
  8. 3 times 3 is 9
  9. 3 times 4 is 12
  10. 3 times 5 is 14 (greater than 13, so we’ll jump to the next number)
  11. 4 times 2 is 8
  12. 4 times 3 is 12
  13. 4 times 4 is 16 (greater than 13, so we’ll jump to the next number)
  14. 5 times 2 is 10
  15. 5 times 3 is 15 (greater than 13, so we’ll jump to the next number)
  16. 6 times 2 is 12
  17. 6 times 3 is 16 (greater than 13, so we’ll jump to the next number)
  18. 7 times 2 is 14 (greater than 13, so we’ll jump to the next number)
  19. 8 times 2 is 16 (greater than 13, so we’ll jump to the next number)
  20. 9 times 2 is 18 (greater than 13, so we’ll jump to the next number)
  21. 10 times 2 is 20 (greater than 13, so we’ll jump to the next number)
  22. 11 times 2 is 22 (greater than 13, so we’ll jump to the next number)
  23. 12 times 2 is 24 (greater than 13, so we’ll jump to the next number)

Now, since none of the numbers we’ve checked multiplied neatly into 13, we can conclude that 13 is a prime number. However, did you notice that after 4, every single potential factor we checked had already been checked in reverse?

For example, 5 times two (line 14) had already been checked (as 2×5) on line 4!

By simply ending the sequence when we start to see the same number again, we half the number of steps needed. If we do this for a bigger number, like 23, we cut it down by 6 sevenths! So as you can imagine,

There were a few other efficiencies I implemented (like not chunking, for example) and there might even be more still (like looking into how the program does long division, and trying to make it easier relative to the problem). But as it turns out, this simple change knocked the program run time from multiple lifetimes to about 3 seconds! So yes, I did find the highest prime number that factors into 600851475143 and I hope that you can too!


I really enjoyed this challenge, and can see myself attempting more in the future (even reattempting the ones I’ve done in order to do them better). I also see myself switching to a lower level language (like C), so that I can program an even faster and more efficient solution (even though it will make doing so more complex). Perhaps this project can be my doorway into really understanding the truly complex mathematics which has hitherto evaded me.

Advertisements

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s