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}`

## No comments:

Post a Comment