## Monday, December 22, 2008

### Project Euler problems 6 - 10

I finally found some time to sit down and do problems 6 through 10 on Project Euler.

Problem 6: Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
``def euler6()  (1..100).inject(0){|val,k| val += k} ** 2 -  (1..100).inject(0){|val,k| val += k**2}end``

Problem 7: What is the 10001st prime number?
``def euler7()  myprime = Prime.new  (1..10000).each{ myprime.next}  myprime.nextend``

Problem 8: Find the greatest product of five consecutive digits in the 1000-digit number.

The 1000 digit number is a string in my code.
``def euler8(bigNum)  len = bigNum.size  stopAt = len - 5  sliceStart = 0  res = 0  while sliceStart < stopAt do      val = 1      s = bigNum.slice(sliceStart, 5)      s.each_char{|x| val *= x.to_i}      res = val if res < val      sliceStart += 1  end  resend``

Problem 9: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
``def euler9()  val = 0  (1..500).each{ |a|      (a..500).each{ |b|          c = (a**2 + b**2)**0.5          next unless c == c.to_i # continue unless c is an integer          val = a + b + c          return a * b * c if val == 1000          break if val > 1000      }   } end``

Project 10: Find the sum of all the primes below two million.

This was the only really challenging problem in this set. I tried to use Ruby's Prime class in a loop for this. When ran for 50,000 iterations it would return in about 14 seconds. For 2,000,000 I eventually killed the process after 15 minutes. The algorithm used in the Prime class seems to fall down when used to generate large lists of prime numbers.

I did some searching and found that most people were using some type of number sieve to generate the list of prime numbers, see Wikipedia here and here. I found and shamelessly stole a Ruby implementation of the Sieve of Eratosthenes from Paul Callagher. I slightly modified Paul's implementation to make it a standalone function instead of a class method.
``# problem 10, find the sum of all primes below 2,000,000.# prime series up to this limit, using Sieve of Eratosthenes method# http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes## from http://tardate.blogspot.com/2008/10/rolling-project-euler-on-ruby.htmldef sieve_of_eratosthenes( maxVal )  limit = Math.sqrt(maxVal)                          a = (2..maxVal).to_a                               n = 2                                              while (n < limit) do                                   x = n*2      begin                                                  a[x-2]=2                                           x+=n                                           end until (x > maxVal )      begin          n+=1      end until ( a[n-2] != 2 )  end  a.uniq!enddef euler10()  sieve_of_eratosthenes( 2_000_000 ).inject(0){|val, x| val += x }end``

This code returns in about 4 seconds.