?

Log in

What is the smallest number that is divisible by all of the numbers from 1 to 20?

« previous entry | next entry »
Oct. 8th, 2008 | 03:32 pm

I recently discovered ProjectEuler which posses mathematical and computer science questions for the eager person to solve. Today I decided to tackle on of them that I've read in the TheDailyWTF.net website:problem 5.

The solution to this is simple and straight forward I think, and doesn't even really need a program, just a calculator. I will give this detailed explanation later, for now, we'll work on the presumption that we are working under heavy pressure from an interview. During an interview, we might not want to sit down and work out puzzles, we probably just want to go straight into the problem and solve it, one way or another. I would be inclined to submit this as a solution, and based on an educated guess that the value can't be greater than 10 million.

  1. #include <iostream>
  2.  
  3. int main( int argc, char **argv )
  4. {
  5. for( int i = 0; i<100000000; i++ ) {
  6. if ( i%2==0 && i%3==0 /* ... */ ) {
  7. std::cout << "Number is: " << i << "\n";
  8. return 0;
  9. }
  10. }
  11. }

But this is absolutely no fun, and a perfectly good waste of time. Instead let's use math as it was meant to be used.

Prime numbers
First we list all the prime numbers from 1 to 20. This is important because for any number to be divisible by two prime numbers (or simply two relatively prime numbers) it must be divisible by their product. In fact, smallest number that is divisible by both of them is their product.

For example: 6 is the first number that is divisible by both 2 and 3. Likewise, 90 is the first number that is divisible by both 9 and 10 because, while neither is a prime number, they are relatively prime to each other.

Ok, so the prime numbers between 1 to 20 are: 2,3,5,7,11,13,17,19.

But we are not finished yet. We can't claim that the product of all these numbers is the solution, primarily, because some of the numbers might be relatively prime with respect to each other. Like 9 and 10, for example. So we move on.

Max prime product

We write down the prime notation of the remaining numbers:

  1. 4 = 2^2
  2. 6 = 2^1 3^1
  3. 8 = 2^3
  4. 9 = 3^2
  5. 10 = 2^1 5^1
  6. 12 = 2^2 3^1
  7. 14 = 2^1 7^1
  8. 15 = 3^1 5^1
  9. 16 = 2^4
  10. 18 = 2^1 3^2
  11. 20 = 2^2 5^1

And the solution will be of the form p^n where p is a prime number and n is the maximum exponent present in the table above. Additionally, we must multiply the prime numbers we identified in the preceding section.

Solution
Mininum divisible of all numbers between 1 and 20 is: (2^4)(3^2)(5)(7)(11)(13)(17)(19).

I guess I should be more scientific and actually remember the lemmas, postulates and theories that make this all happen. Maybe next time ;)

Link | Leave a comment | Share

Comments {0}