Project Euler

I recently found out about Project Euler which has a collection of math/programming problems to solve. I have started working through the problems using Ruby. I have decided on using Ruby in my current project, which I will do some posts on later, but I don't have any real experience using it, so this will give me something to work with while learning the language.

The first problem: Sum all integers less than 1,000 that are multiples of 3 or 5. This is my third version and I have it down to a single line.

(1..999).inject(0){|result, n|
   (0==n%3 or 0==n%5)? result + n : result}

The second problem: Sum all even numbers in the Fibonacci sequence that do not exceed 4,000,000. My first solution uses a recursive algorithm.

def euler2_rec(n1=1, n2=1)
  return 0 if n1 > 4000000
  fib = n1 + n2
  sum = euler2_rec(n2, fib)
  sum += fib if 0 == fib % 2
  return sum
end

Since this is tail recursive and any tail recursive algorithm can be converted to a loop. I decided to create a loop version.

def euler2_loop
n1 = 1 
n2 = 1
sum = 0
begin
    fib = n1 + n2
    sum += fib if 0 == fib % 2
    n1 = n2
    n2 = fib
end while fib < 4000000
return sum
end

The third problem: Find the largest prime factor of 600,851,475,143. For this I used Ruby's Prime class.

def euler3()
  num = 600851475143
  primes = Prime.new
  factor = 0
  while num > 1 do
     factor = primes.next
     num /= factor if 0 == num % factor
  end
  return factor
end

I had originally used num / 2 as my halting condition. But reading the comments after solving the problem I saw that others divided out the factors as they found them. This allows the loop to exit after the largest factor is found, and is rather obvious once you see it.

The fourth problem: Find the largest palindromic number that is made from the product of two 3-digit numbers.

def euler4()
 result = 0
 100.upto(999) { |i|
   i.upto(999) { |j|
     val = i * j
     result = val if result < val and
         val.to_s == val.to_s.reverse
  }}
 return result
end

The fifth problem: Find the smallest number that is evenly divisible by all numbers between 1 and 20.

The easy and obvious approach for this problem is to take each number and test it to see if it evenly divisible by the numbers 2 to 20, all integers being evenly divisible by 1. One can think of some optimization that can be applied to this approach. For example a number must end in a 0 to be evenly divisible by 10. Also any number that is evenly divisible by 20 is also divisible by 10, 5, 4, and 2. Also one can consider that all, non prime, numbers can be factored into prime numbers. So the problem can be reduced to working with a set of prime numbers.

However, I wasn't sure of the correct approach, and being too lazy to get off of the couch to crack open a dusty old math book, I opted for brute force and ignorance and wrote program to iteratively check all numbers. While that was chewing up my CPU in the background I searched for a better solution and found this blog post on the problem. The solution proposed in that post is to find the accumulated least common multiple (LCM) for the numbers 2 to 20. A bit more searching turned up this page which had sample code, in Ruby, which would calculate the LCM and greatest common factor (GCF). So a little bit of time later, and with my original code still running, I had this solution.

require "gcf_lcm.rb"
def euler5()
  lcm = calc_lcm(2,3, calc_gcf(2,3) )
  4.upto(20) { |n|
    lcm = calc_lcm(lcm, n, calc_gcf(lcm, n) ) }
   return lcm
end

This returns almost instantly, and with the correct answer. When looking through the comments on this problem I found a posting with a Ruby solution. It turns out there are library routines in Ruby for LCM and GCF and the solution can be turned into a one liner.

(2..20).inject(1){|res,n| res.lcm n}