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.
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