Books I Like

Monday, October 19, 2009

Solving Project Euler Problem #5 in Ruby

The problem statement :

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?

Solution/s :

One of the solution is straight forward as Ruby exposes such a nice library (Actually it feels like a cheat :))


require 'rational'
puts (1..20).inject(1) { |result, n| result.lcm n }


The other solution involves a little bit of math/algorithm. Hopefully you will enjoy it.


#
# Directly using the ruby library
# require 'rational'
# puts (1..20).inject(1) { |result, n| result.lcm n }
#
# The other solution (Code below) Steps :
# 1. Fetch all the primes less than "n" in an array (it would be automatically sorted, which will save our efforts later)
# 2. For the smallest member "k" of the prime list, find the maxm power "m" such that k**m <=n (For, e.g. 2**4<20)
# 3. Replace the smallest member from the array with k**m (For e.g. replace 2 with 16, because anything divisible by k**m
# would be itself be divisible by k**0..m-1)
# 4. Repeat the steps 2-3, for the next member of the array (starting with the power #m-1). when the power becomes 1, no need
# to iterate.
# 5. Multiply the members of the final array.
#
# Sample runs :
# For n = 10
#
# All the primes :
# [2, 3, 5, 7]
# All the multipliers :
# [8, 9, 5, 7]
# 2520
#
# For n = 20
#
# All the primes :
# [2, 3, 5, 7, 11, 13, 17, 19]
# All the multipliers :
# [16, 9, 5, 7, 11, 13, 17, 19]
# 232792560
#

require 'mathn'

def collect_primes(n)
primes_list = []
primes = Prime.new
primes.each { |x| break if x >= n; primes_list<<x; }
puts "All the primes :"
p primes_list
primes_list
end

def root(arg, base)
arg**(1/base)
end

def get_all_the_multipliers(n)
primes_list = collect_primes(n)
max_base = get_max_base_for_two(n)

primes_list.each_with_index do |item, index|
primes_list[index]=item**max_base
max_base = get_max_base_for_current_number(n,max_base,primes_list[index+1])
if max_base <=1 then break
end
end
puts "All the multipliers :"
p primes_list
primes_list
end

def get_mulitiplied_value(n)
list_of_multipliers = get_all_the_multipliers(n)
list_of_multipliers.inject(1){|total, i| total*i}
end

def get_max_base_for_two(n)
i=2
while root(n,i) >= 2
i = i+1;
end
return i-1
end

def get_max_base_for_current_number(n,max_base, current_number)
base = max_base - 1
while current_number**base > n
base = base - 1
end
return base
end


puts get_mulitiplied_value(20)
#puts get_mulitiplied_value(10)



Comments are welcome .

3 comments:

Mat Schaffer said...

You can use Symbol.to_proc to make that shorter.

(2..20).inject &:lcm

of course jeff told me that was cheating. But thanks to wikipedia writing my own lcm was trivial.

Anonymous said...

you need a rubyism:
(1..20).the_smallest_number_evenly_divisible_by_all_of_the_numbers()

Steven said...

Using lcm is a cheat since that is the program you are really producing.

a clojure general solution might look something like this:


(defn euler-5 [m]
(let [prime-pow-fn (fn [x] (loop [acc x] (if (> (* x acc) m) acc (recur (* x acc)))))
primes (take-while (fn[x] (<= x m)) '(2 3 5 7 11 13 17 19))]
(reduce * 1 (map prime-pow-fn primes))))



'(2 3 5...) should be a lazy prime # sequence


Yet again, map/reduce to the rescue.

Get at Amazon