I was stuck on this one for way too long. I was able to figure out a brute force approach quickly enough, but it was taking forever. Finally after hours (told you I took way too long!) of scratching around in my notebook before I had my eureka moment. I basically just determined that the least common multiple between 2 contiguous numbers must be a factor of my final result, and from there I just stepped my way up the chain. It’s running in about 24ms on my machine!

I also determined that I didn’t need to check any numbers under 1/2 of the given number 20 since they were already factors of the higher numbers, but that doesn’t actually effect the Big O and the timing difference is negligible.

PS: Yes, I used the exact library that I accused Olathe and Mat of “cheating” for on Problem #4. Shush!

Problem #5

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 number that is evenly divisible by all of the numbers from 1 to 20?

 require 'mathn'

max = 20
min = (max / 2).floor + 1
n   = min

(min..max).each do |i|
  n = n.lcm i
end

puts n 

I was pretty proud of this solution and given all the incarnations this program’s been through I thought it came out really nice…until (you guessed it) I saw Olathes!

 require 'rational'
num = (1..20).inject(1) { |result, n| result.lcm n }
puts "Smallest evenly divisible number is #{ num }."

It’s been a number of years since my last math class, so I had to bust out the pen and paper. I figured that for given number n you can stop checking for factors after n / 2, but I didn’t realize till much later (and by “realize”, I mean read up on prime numbers) that you can actually stop checking for prime factors at the square root. This saves considerable time when you’re dealing with numbers in the quadrabazillions. It’s the difference between < 2 seconds and I-did-the-dishes-and-it's-still-running. On a side note, I don't consider reading up on the subject "cheating". I consider looking up algorithms and other solutions "cheating". Problem #3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

target = 600_851_475_143

def find_highest_prime_factor n
  (Math.sqrt(n).ceil).downto 2 do |i|
    if n % i == 0 && find_highest_prime_factor(i) == 1
      return i
    end
  end
  1
end

puts find_highest_prime_factor(target)

As expected, Olathe delivers. Runs roughly 3 times as fast and is easier on the eyes…even though he loaded an external library (cheater!)

 require 'mathn'
num, factor = 317_584_931_803, 0
primes = Prime.new
while num > 1
  factor = primes.next
  num /= factor while (num % factor).zero?
end
 
puts "Largest factor is #{ factor }."

However, if you’re going to cheat…cheat big! Posted by mat:

 require 'mathn'
317584931803.prime_division.last[0]

**UPDATE**
The two not-mine solutions use a different number (317584931803. instead of 600851475143) so the solution is different, but the algorithms are correct.

My solution for Project Euler problem #2 came out a little fugly mainly because of the global variables, but it works. The “secret” to getting the program to run in a reasonable amount of time is to store the values of the fibonacci sequence as you compute them instead of processing the same data over again.

Problem #2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My Solution

max    = 4_000_000
total  = 0
$stack = []

def fib n
  if n == 0
    return 1
  end
  if n == 1
    return 2
  end
  return $stack[n - 1] + $stack[n - 2]
end

max.times do |i|
  $stack[i] = fib i
  if $stack[i] > max
    break
  end
  if $stack[i] & 1 == 0
    total += $stack[i]
  end
end

puts total

As is quickly becoming the case, Olathe’s solution was much more elegant than mine:

x, y, sum = 1, 1, 0
while sum < 1_000_000
  sum += (x + y)
  x, y = x + 2*y, 2*x + 3*y
end
 
puts "Sum is #{ sum }."

I’ve been working through some of the Project Euler problems in Ruby and I thought I’d post my solutions. I refuse to “cheat”, but it’s really neat to see all the different ways other people solve the problems afterwards.

Problem #1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

total = 0

1000.times do |i|
  if i % 3 == 0 || i % 5 == 0
    total += i
  end
end

puts total

I googled around a bit after I finished and particularly liked this solution, which seemed more ruby-ish to me:

answer = (0..999).select { |a| a%3 ==0 || a%5==0 }
puts answer.inject { |sum, n| sum+n }

And, from the forums I thought Olathe’s solution was really neat, although mathily over my head:

class Integer
  def sum_mod modulus
    n = self.div modulus
    modulus * n * (n + 1) / 2
  end
end
 
num = 999
sum = num.sum_mod(3) + num.sum_mod(5) - num.sum_mod(15)
 
puts "Sum is #{ sum }."