#### Description

From Project Euler: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?

#### Solution

Another name for the smallest number that is evenly divisible by two or more numbers is the least common multiple (LCM). In general, finding the least common multiple is an easy task if we make the following observation. All numbers greater than 1 can be expressed uniquely as the product of its prime factors.10 => 2, 5 => 2 x 5

In addition, each prime factor may have an exponent greater than one.

90 => 2, 3, 3, 5 => 2

^{1}x 3

^{2}x 5

^{1}

To find the least common multiple of two or more numbers, you take the prime factorization of each number, than multiply the highest exponent of each prime together. This gives the least common multiple. (For more information on how this works, see this Wikipedia article).

8 => 2, 2, 2 =>

**2**

^{3}18 => 2, 3, 3 => 2

^{1}x

**3**84 => 2, 2, 3, 7 => 2

^{2}^{2}x 3

^{1}x

**7**

^{1}lcm(8, 9, 21) => 2

^{3}x 3

^{2}x 7

^{1}=> 504

We already created a method that can compute the prime factors for us in problem 3. However, now, we don’t want to simply list them, we want to list the factors exactly once with their associated exponent. To do this, we’ll change the prime_factors method to instead return a hash. The keys of the hash will be the prime factors, and the values will be the exponent.

class Integer def prime_factors prime = 2 result = {} value = self while value >= prime ** 2 if value % prime == 0 result.merge!(prime => 0) if not result.has_key?(prime) result[prime] += 1 value /= prime else prime += 1 end end result.merge!(value => 0) if not result.has_key?(value) result[value] += 1 return result end end

600_851_475_143.prime_factors.keys.max

Now the method for computing the least common multiple becomes trivial:

class Problem005 def lcm(*numbers) factors = {} numbers.each do |n| factors.merge!(n.prime_factors) do |key,x,y| x > y : x : y end end factors.inject(1) { |product,pair| product * (pair[0] ** pair[1]) } end end Problem005.new.lcm 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

The full source and specifications can be seen on github. Next time, the difference between the sum of squares and the square of sums.

## No comments:

Post a Comment