Project Euler Problem No.5

Standard

Consider the numbers you have to test:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Break up the composite numbers to prime factors:
1, 2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5,
11, 2*2*3, 13, 2*7, 3*5, 2*2*2*2, 17, 2*3*3, 19, 2*2*5

For a number to be divisible by each of these groups, they have to show up among the prime factorization of our number.

The smallest number divisible by 1, 2, and 3 is 1*2*3 = 6.
To find the smallest number divisible by 1, 2, 3 and 4, we don’t have to multiply all of them together because there’s some redundancies. (2,2,3) is the smallest set that includes the sets (2), (3) and (2,2). So 2*2*3 = 12 is the smallest number divisible by 2, 3 and 4.

There are no 5s in the set (2,2,3), so the first number divisible by 1 through 5 has to be (2,2,3,5) = 60.

6 is 2*3, and we already have that, so we’ve found the number divisible by 1 through 6. Since 7 is prime, our new number has to be (2,2,3,5,7) = 420 in order to be divisible by everything up through 7.

8 is 2*2*2, so in order for (2,2,2) to be a subset we need to add one more two to get (2,2,2,3,5,7).

Continue on like this to get (2,2,2,3,3,5,7) for 9, which is already set for 10=2*5. 11 is prime, so we have (2,2,2,3,3,5,7,11). We’re all set for 12, because 12=2*2*3 and we have two 2s and a 3. For 13 we need (2, 2, 2, 3, 3, 5, 7, 11, 13). This already includes the factors of 14=2*7 and 15=3*5. For 16 we need an extra 2, to get (2, 2, 2, 2, 3, 3, 5, 7, 11, 13).

Then to 17: (2, 2, 2, 2, 3, 3, 5, 7, 11, 13). 18 is all set. 19 makes it (2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 19). And 20 is all set because we already have (2,2,5).

So the shortest number is
2*2*2*2 * 3*3 * 5*7*11*13*19 = 1,3693,680

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s