Project Euler #5 – A Fool Remains

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?

 

He who asks is a fool for five minutes, but he who does not ask remains a fool forever.

Chinese Proverb

 

This is an example of why students hate word problems. It’s also an example of why it’s important to practice with word problems.

You see, it’s not just about asking a question. It’s about how the question is framed. Question framing can make a big difference in how easy it is to find the answer. This is related to (but not the same as) the loaded question, which is one of the classic logical fallacies.

So when I come across a problem like this, I try to rephrase the question in such a way that my path to the answer becomes more clear. In this case, the question makes more sense to me when phrased like this:

What numbers can be factored into the first 20 integers? Find the smallest one.

Since I’m lazy, I asked WolframAlpha but it didn’t understand the question. I also considered that multiplying all of the numbers from 1 to 20 together (otherwise known as 20 factorial or 20!) would answer the first part of the question but not the second. (It’s 2432902008176640000, by the way.) (Yeah, probably too big.)

Now, of course, I have a computer that has no problem with mindless arithmetic so I could totally brute-force this by starting at 2520 (since the answer certainly can’t be smaller than that), factoring each number, examining the factors to make sure all required integers are present and so on. But I think there’s a lazier (and hence smarter) way of doing this.

Consider that certain factors automatically get us other factors for free:

20 – gives me 2, 4, 5 and 10

18 – gives me 2, 3, 6, and 9

16 – gives me 2, 4 and 8

14 – gives me 2 and 7

15 – gives me 3 and 5

9 – gives me 3

And so on and so forth. Let’s try that technique with a number we already know, 2520 and the factors from 1 to 10.

10 – gives me 2 and 5

9 – gives me 3

8 – gives me 4

7 – a prime but needs to be in there because we don’t get it anywhere else

6 – got it (2 from 10 and 3 from 9)

5 – got it (from 10)

4 – got it (from 10 via 2 and from 8)

3 – got it (from 9)

2 – got it (from 10 and 8)

1 – duh

So the factors that I care about are 10, 9, 8 and 7. If we multiply these together we get 5040. Not the answer we’re looking for but certainly better than 10! (otherwise known as 3,628,800). My keen eye, however, observes that 5040 is exactly twice 2520, so I have an extra 2 somewhere in my numbers that I don’t need. (I’m going for smallest, after all.) Well, I already get a 2 from the 10 so I don’t need 8. But now I don’t have a 4 (almost sounds like we’re playing Fish) so I’ll substitute to get the factors 10, 9, 7 and 4. Multiplying these together gives us 2520 which is the correct answer.

This is a problem-solving technique I like to use when I want to experiment with solutions. Find a similar, but smaller problem (preferably one where you already know the answer or can easily get to it) and use it as a test case.  (Make sure your logical assumptions are sound, though.)

I think I’m ready to tackle the original problem now. I’m going to use a table so that I can organize my factors more efficiently

 

Factor

Gives me

20

2, 4, 5, 10

19

19

18

3, 6, 9

17

17

16

2, 4, 8

15

3, 5

14

2, 7

13

13

12

2, 3, 4, 6

11

11

10

2, 5

9

3

8

2,4

7

7

6

2,3

5

5

4

2

3

3

2

2

1

duh

Since we don’t get 19,17, 13 and 11 from anywhere else, they have to be part of our final answer. Let’s look at that table again and mark off the numbers we need and don’t need.

Factor

Gives me

20

2, 4, 5, 10

19

19

18

3, 6, 9

17

17

16

2, 4, 8

15

3, 5

14

2, 7

13

13

12

2, 3, 4, 6

11

11

10

2, 5

9

3

8

2,4

7

7

6

2,3

5

5

4

2

3

3

2

2

1

duh

 

So it looks like we just need 19, 18,17,13,11,10,8 and 7. Multiplying these together gives us 465,585,120. A quick calculation at WolframAlpha confirms that the first 20 integers are indeed factors of this number. This seems like a large number but not when compared to 20!, which is  2.43290200817664 × 10^18 or a bit over 2 quintillion.

So that’s definitely an answer, but is it the answer? Based on our experience with the smaller version of this problem, let’s try to substitute 4 for 8 as one of our factors. This gives us 232,792,560 which is not only smaller but is also correct. But can we keep going down? A bit of experimentation shows that with further substitutions cause factors to drop out so that’s no go. So we end up with 19,18,17,14,11,10,4 and 7.

So we looked at a couple of problem-solving techniques that we can add to our intellectual toolkits:

  • If possible, rephrase the question so that it suggests a path to the answer

  • Use a smaller version of the problem to quickly test your potential solutions.

  • As always, use a computer for the boring stuff.
Advertisements

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