Project Euler Problem 10

Here follows the story of problem 10, an epic tale spanning two countries and involving my mother in law! In my ongoing attempts to master Ruby through the solving of Project Euler tasks, I had hit a little snag on this problem. “This problem sounds easy!” I thought, and I wrote the code out in a clean, readable style just as I promised, hit run and… oh.

One of the rules of Project Euler is that your code needs to finish in under a minute in order to count, and my code was still running after two. My original prime calculating code was clearly too inefficient to cut it under this level of complexity. It is at this point that I was forced to confront the fact that I am, in fact, shit at maths. All I knew about prime numbers is that they were real integers which are divisible by only 1 and themselves. That was, literally, it. I knew nothing of their inherrent properties beyond that. Was this to be the problem where my lack of mathematical knowledge stopped me in my tracks?

I was very keen to solve this on my own rather than googling, so I reasoned like this: If i can’t solve this with mathematical knowledge, maybe i can solve it by thinking like a programmer. My initial thoughts were;

* Iterating over large arrays is expensive
* Arithmetic, when done on a large scale, is expensive
* Comparisons are very cheap

I then started to work in any knowledge of maths I had into the solution: I knew that Ruby would very competently be able to handle an array of 2 million real numbers. The plan was to start with an array of all numbers up to 2 million, then “zero them” when i knew they weren’t prime. At the end, it would just be a case of adding up all of those numbers that weren’t zero. This would be more efficient than my existing prime method, which involved iterating through all numbers prior ot the one you’re calculating.

At this point I was still using my original prime method to do this, and I knew that this was computational overkill, so I started to think of other ways to do this. I know that all even numbers (with the exception of 2) are not prime. Therefore, when i initialize the array, I can get rid of the evens from the start. That’s half the problem solved, right?

Still not quick enough. It is at this point that I realized that my prime calculating method had got to go. I was all but ready to give up, but then had a bit of a brainwave during a long drive to Wales (hey, it’s inspiring country!). While I am iterating from 3 to 2m, I can also reason that any multiple of the number I am currently on (up to 2m) can also be zeroed. Then, as I iterated further, I could skip over those that were already zero with another nice cheap comparison. This would make the algoritm slow at first, but super-fast once it got going. When I eventually got to Wales I was so excited about it that I described the whole algorithm to my in-laws (who were also in Wales). In hindsight, they probably thought I was a total freak, but my mother in law did draw a comparison between the algorithm and the childrens game “Guess who”, which is an awesome comparison it has to be said!

I started coding as soon as I could, and my little netbook finally managed to calculate the sum of primes below 2 million in 32 seconds!

In an interesting epilogue to the story, once you solve a Project Euler problem you are invited to a forum thread to gaze in awe at other people’s solutions. Many of the other participants were talking about something called the Sieve of Eratosthenes, so I decided to google it. I was quite suprised to find that the solution I had come with on the drive to Wales was actually an implementation of this 2000 year old greek algorithm!

In retrospect, I nearly buckled and gave in a couple of times on this but I am so pleased that I didn’t. I am not really doing this to learn maths, I’m doing it to learn ruby, but if gaining a better understanding of mathematical algorithms is a happy side-effect then who am I to argue. The feeling of elation for having come up with this solution on my own is pretty phenominal, even if it did mean breaking my promise about writing readable code!

Incidentally, the plan is not to post every single problem solution that I come up with, only those I’m particularly proud of or that hold some kind of merit worth mentioning. Anyway, here is my solution, in all its unreadable glory 🙂 There is a commented puts in there which, if you uncomment, will show you how this algorithm builds speed as it closes off the multiples.

def problem10

  puts "start: " + Time.now.to_s

  # create array of numbers 1 - 2m
  two_million = 2000000
  
  #set up the array
  arr = []
  (1..two_million).each do 
    |num| 
    if ((num.even? and num != 2) or num == 1)
      arr << 0
    else
      arr << num
    end
  end
  
  #start the iteration
  3.step(two_million, 2) do

    |index|
    
    next if arr[index-1] == 0

    current_number = arr[index-1]
    total += current_number

    #uncomment next line to see the algorithm gaining momentum!
    #puts current_number

    multiplier = 3

    while true do

      result = arr[(multiplier*current_number)-1]

      break if result == nil

      arr[result-1] = 0

      multiplier += 2      

    end

  end
  
  puts total

  puts "Finish: " + Time.now.to_s
  
end

It is worth noting that there are further optimizations that can be done to the above. The array initialization, for example, only initially zeros even numbers. Knowing, for example, that all multiples of five are not prime, those numbers ending in 5 could also be eliminated at this stage (you’d have already gotten rid of the numbers ending in zero when you blat the evens). One such algorithm that reasons along the same lines is the Sieve of Atkin, for anyone who wants to check it out.

Advertisements

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