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

A basic approach to this problem would be to just start at 20 and increment, checking each number if it divides evenly by each of the numbers 2..20

n = 20
while(1)
return n if (2..20).to_a().delete_if{ |x| n%x == 0 }.count() ==0
n += 1

problem is, it’s a big number.

The question actually asking us for least common multiple. Time for a refresher on grade school math:
lcm(2..20 can be computed by
– find prime factors for all numbers 2..20
– multiply each prime factor the maximum number of times it occurs in one of the numbers
Since we already wrote a function that findes prime factors in problem 3 we just need code for step 2:

factors = {}
 
for i in 1..20 do
	fl = listfactors( i )
	fh = Hash[fl.map{ |x| [x, fl.count(x)] }]
	factors.update(fh){|key, v1, v2| [v1, v2].max }
end
n = 1
factors.each{ |k,v| n *= k**v }
puts n

A small optimization on this code might be to generate all the factors at once and divide them out of the list since counting the number of times each factor occurs is a bit wasteful.

I have not implemented it, but there’s an even better approach: It turns out that least common multiple and greatest common denominator are related with a simple formula:
– lcm(a,b) = |a*b|/gcd(a,b)
And greatest common denominator is a very fast calculation using Euler’s iterative algorithm

def gcd(a,b) #assumes a > b
   c = a%b
   return b if c == 0
   return gcd(b,c)
end

There’s also a variation on this algorithm that uses bit shifts rather than division, for a bit more efficiency.


About this entry