Find the greatest product of five consecutive digits in the 1000-digit number.
At first glance this appears to be arithmetic which, as we all know, is boring and mechanical and completely beneath us as humans. Well, actually, at first glance the part of our brains that does arithmetic (you know, the boring part) sees this awful number and just wants to shut down. Since I knew it had to be more than just arithmetic, I tucked it in the back of my mind to ferment a bit before tackling it again.
After a bit of thought, I can see the trick here. The problem statement refers to a 1000-digit number but we’re supposed to deal with individual sets of digits. So we can use math to make this more interesting (since math makes everything better) and simply regard this as a string of 1000 digits.
How does this help? First of all, any string of digits with a zero in it we can disregard. In fact, we can discard any ten consecutive digits that have a zero in the middle since any five digit sequence will multiply out to zero. So we look for digits with this pattern:
Let’s take another look at our number, clearing out digits within four positions of any zero:
Okay, I’ve eliminated all strings of digits whose product will be zero so our new string of digits becomes:
(I could have written a script to do this for me but pattern-matching is part of my evolution so I can do it myself without much trouble.)
This is a much more manageable number (still 389 digits long, though) but if we’re ultimately going to be doing arithmetic (and it looks like we’ll have to eventually) we have to think about having a machine do the work and that involves explaining the task to a machine in a way that it can understand. But this brings us to a question:
Do we really have to do any arithmetic at all?
A bit of thought tells us that we may be able to avoid arithmetic after all. Here’s the logic:
Start scanning the string of digits and split off each set of five. For example, if our string was:
We would pull out the substrings:
Now, remember, I don’t really want to any arithmetic if I can help it so I do a bit of math thinking and rearrange the numbers in sorted order:
I can multiply numbers in any order I want so rearranging the digits won’t change the outcome. However, by sorting numerically, the number with the largest magnitude will automatically give me the largest product. 77661 is the largest number in my sequence here but let’s test my hypothesis just to check my thinking:
Original Sorted Product
73167 77631 882
31671 76311 126
16717 77611 294
67176 77661 1764
Sorting has the added benefit of letting us eliminate strings that have the same digits (and thus the same product). So I only need to find the largest five digit number (after sorting) and then get the product of those five digits. I have now knocked my job down to doing a single multiplication and I bet I can get my computer to do even that little job for me if I’m feeling particularly lazy.
So I just whipped up a quick script to dump out 386 separate five digit strings of digits and sort each set of strings numerically. Then I copied and pasted the output into a spreadsheet and did a quick numerical sort to find the largest numerical quantity. Here is my result:
It’s then a simple matter of using my hand-dandy calculator and determining the product, which is 10,206.
So we took a problem that looked like it would require almost 1000 arithmetic operations and knocked it down to a single calculation with just a bit of thought about the conditions of the problem.
If anyone is interested, I’ve posted my script here.
See, math makes everything better!