Wild About Math! Making Math fun and accessible

6Jun/092

MMM #33: We have a winner!

Random.org picked Nikhil Chelliah as the winner for MMM #33. Congratulations, Nikhil!

Here is the problem description:

What’s the prime factorization of the smallest whole number that is divisible by all integers from 1 up to and including 50?

Here is Nikhil's solution:

The least common multiple of a group of numbers, has, for each prime factor, as many occurrences as the greatest of the group of numbers. Which may make sense iff you already know what I'm talking about.

One algorithm would involve finding the prime factorization of each number up to 50, then taking the most occurrences of each prime factor and producing a final result. A more elegant solution involves identifying all the prime factors without calculating the prime factorization.

The prime factors are simply every prime number up to 50, since all of those numbers are factors, but we don't care about the composites. Then, for each prime, we ask, what's the maximum number of times this prime appears in any of the factors?

To answer this we find the greatest exponentiation of the prime number that remains at or below 50. For 2, this is 32; for 3, it's 27, etc. To find it, we do greatest-integer on the log-base-n of 50.

The following Python code finds all the primes below 50 and their maximum integer exponentiations below 50, and prints each prime that many times.

from math import sqrt, log, floor

def is_prime(n):
if n == 1:
return False
for factor in xrange(2, 1 + sqrt(n)):
if n % factor == 0:
return False
return True

numbers = range(1, 51)
primes = filter(is_prime, numbers)

factors = []
for prime in primes:
for i in xrange( floor( log(50, prime) ) ):
factors.append(prime)
print factors

And the result is:

2, 2, 2, 2, 2, 3, 3, 3, 5, 5, 7, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Many of you wrote the answer more concisely as:

2^5 * 3^3 * 5^2 * 7^2 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47

A number of you noted that I was asking you to find the least common multiple (LCM) of the numbers from 1 to 50. Amit Mahajan (and Caleb Rascon) also noted that each of the numbers from 1 to 25 divide at least one of the numbers between 26 and 50 so the problem can be restarted as finding LCM(26,27,28,29,30,...,49,50) and then Amit proceeded to find the LCM of these numbers in an interesting manner. See if you can understand Amit's approach from this picture.

Ms. J at sinesoflearning.blogspot.com created a nice illustration of how she approached the problem although she did make a leap of faith in going from step 1 to step 2.

Benjamin Scott showed how Wolfram Alpha can give an answer. Very clever, Benjamin!

Chris Hatfield solved a more general problem with Matlab.

This MATLAB program is set to do more than the initial question. More than just finding the smallest whole number divisible by all integers from 1 to 50, this code will take an inputted start number and end number, which must be integers, and find the smallest whole number divisble by all integers in between the two numbers, including the numbers themselves.

The way this code works is by taking all the numbers from the start number to the end number, taking the prime factorization of each number. Finding out the maximum number of times a prime number shows up in any one factorization, then multiplies the prime number raised to its max number of times it shows up in one factorization together, finally giving a message telling you the number and the prime factorization of that number.

Leave a comment on this blog article if you want Chris' Matlab code and I'll forward your request to Chris.

Stay tuned for MMM #34 at Blinkdagger on Monday!

Comments (2) Trackbacks (0)
  1. I lost again? This is getting ridiculous.

    NS

  2. Hi,
    I solve the general problem of finding the smallest number divisible by the first n natural numbers. I write up the solution here: http://watchmath.com/vlog/?p=267

    Thanks


Leave a comment

No trackbacks yet.