Contract Work

Tuesday, October 22, 2013

Halfway there. Euler 5.

Euler 5! Phew, so, this marked my halfway point through the 10 problems I decided to do in Project Euler.

So, here is the problem:

2520 is the smallest number that can be divided by each of the numbers 
 from 1 to 10 without any remainder.
 What is the smallest positive number that is evenly divisible by 
 all of the numbers from 1 to 20?
For this problem, I actually solved it in a really ugly, awful way and then went back to refactor . I can't remember exactly but I think the ugly way involved taking a range of numbers, multiplying all of them and then seeing which was the smallest that had a remainder of 0 for each of the numbers... whatever it was, it was super complicated. Anyway, so first, the tests:

require 'problem5/problem5'
describe 'lowest common multiple' do 
  it "find the smallest number that can be divided by 1 through 10 with no remainder" do 
    expect(Problem5.divided_by(1...10)).to eq 2520

  it "finds the smallest number that can be divided by 1 through 20 with no remainder" do 
    expect(Problem5.divided_by(1...20)).to eq 232792560

At this point, if you've been reading the Euler series of this blog, you'll notice a pattern to all of the tests. This may not be the most sophisticated way to execute the tests since rspec can do a lot of cool things, but using the same format worked for and was a way I became comfortable with seeing tests formats, running the tests, etc.

Now for the answer:
module Problem5

def self.divided_by(number_range)
  list = (number_range).inject(:lcm)
  return list

puts Problem5.divided_by(1..20)


so, once I started reading the ruby docs, I noticed there was a greatest common denominator and a least common multiple method with an integer. Looking into those, the least common multiple method was a perfect, simple way to solve this problem. The inject plus LCM method on an integer basically takes a list and finds the lowest common multiple of that range of numbers.

1 comment:

  1. I think you would learn more if you implemented all the required functions. In problem 3, for example, you used require 'prime'. This way, you deprived yourself the opportunity of realizing that the naïve factorization method wouldn't work with that problem.

    I'm watching you repo on github, waiting for new solutions :)