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.

Project Euler #4 – Red Rum, Sir, is Murder

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
Find the largest palindrome made from the product of two 3-digit numbers.

This seems like an odd problem (no pun intended). My goal with this series, if you recall, is not just to solve problems from Project Euler (http://www.projecteuler.net) but to figure out the deeper meaning behind each problem. This time I think the solution to the problem may lie in some deeper thinking about the numbers themselves.
You see, there really is no strictly mathematical significance to palindromic numbers. They are only important to people who do math for fun. (Yeah, I know.) In fact, there’s an entire field of study(?) known as recreational mathematics. For those of you out there who hate and/or fear math, this must sound like a seriously strange hobby only slightly less deranged than those people who collect shrunken heads. You’d think so, but if you’re a fan of Sudoku or other logical puzzles, then you’re a fan of recreational math.
But if we give these poor souls the benefit of the doubt, recreational mathematics is a way to move beyond the strictly technical operations of mathematics and explore the deeper relationships between numbers and our human world.
Anyway, back to considering palindromic numbers. A bit of thought tells us that all single-digit numbers are palindromes, so there are 9 single-digit palindromes. For two digit numbers, there are also 9 palindromes (11, 22, 33, 44, etc). For three digits, it starts to get more complicated but let’s think it out.
Our starting digit must be our ending digit so this gives us 9 possible templates such as 1_1, 2_2, 3_3, etc. The middle number can be anything we want so there are 10 possibilities there (don’t forget 0!) so each of our nine templates can be formed into ten different numbers. So the total number of 9 x 10 or 90 possible palindromic three-digit numbers.
I’m starting to see a pattern here. Maybe we can use this technique to narrow down our possible answers to where we’ll know it when we see it. In other words, what should our answer look like? (This is an excellent technique for real, practical math as well since it lets you recognize the answer when you see it.)
Our number will be a palindrome. (Okay, baby steps first. By the way, recognizing palindromes is one more of those things that humans are much better at doing than computers.)
It will be the product of two 3-digit numbers, as stated. So, the first question I might ask at this point is ‘How many digits will our number have?’ I mean, sure, I could write a program that would multiply every possible pair of 3-digit numbers, check each result for palindromicity (yes, that’s a word….now) and just print that out but where’s the fun in that? So I can say for sure that my answer will have at least five digits [ 100 x 100] and no more than six [999 x 999]. Given that we’re looking for the largest number, we can restrict our search to 6 digits.
Consider, however, that we’re looking for the largest palindromic number. So it seems like a good bet that it will start and end with 9. Combine that with my previous assumption and my number will look something like 9xxxx9 (where each x is some digit between 0 and 9). So this gives us a range between 900,009 and 997,999 so we have almost 98,000 possibilities. This is a large number, sure, but is better than our previous field of over 980,000 so we’ve knocked ninety percent off of our search range. We can also ignore prime numbers (why, boys and girls?) and WolframAlpha tells me that there are 7083 primes in our range so that knocks our search space down by a little bit.
Now WolframAlpha tells me that 900,009 isn’t the product of two 3-digit numbers. So assuming I don’t want to just start multiplying at 100 and go up from there, where do I start? I’m planning on having a computer do the grunt work so I’m not too concerned about how much arithmetic I have to do but I want the solution in my current lifetime. (Netflix isn’t going to watch itself, you know.)
So time for more thinking. Does it really matter where I start? I want a pair of 3-digit numbers that are likely to be a bit less than the right answer because I’m going to let my computer sneak up on the real answer by brute force. So let’s set both numbers to 900. (Sort of the math equivalent of Kentucky Windage. Oh, yes, that’s a thing.) What do I tell my computer? I think the logic should go something like this:

A=900
B=900
C=0
PALINDROME=0

{Keep going until I tell you to stop}
C = A * B
{Is C a palindrome AND bigger than PALINDROME?}
Yes: C becomes the new value for PALINDROME
No: B = B + 1
{Is B = 1000?}
Yes: reset B to 900 and add 1 to A
{Keep doing the above until A = 1000}

Print out our answer

I think we have enough information to jump in and do this now. I created a little script and this was the result:

906609 is the largest palindromic number that is a product of two three-digit numbers (993 and 913).

Just out of curiosity (and being an enormous nerd), I ran the script again with a timer and got:

real 0m26.480s
user 0m11.793s
sys 0m17.230s

For those of you who are interested, here’s a link to the script.

So what did we learn?

  • Recreational math is more common than you think.
  • Humans are still smarter than computers.
  • Putting a little thought on the front end into solving a problem makes for less work on the back end.