*Find the greatest product of five consecutive digits in the 1000-digit number.*

*73167176531330624919225119674426574742355349194934
*

*96983520312774506326239578318016984801869478851843*

*85861560789112949495459501737958331952853208805511*

*12540698747158523863050715693290963295227443043557*

*66896648950445244523161731856403098711121722383113*

*62229893423380308135336276614282806444486645238749*

*30358907296290491560440772390713810515859307960866*

*70172427121883998797908792274921901699720888093776*

*65727333001053367881220235421809751254540594752243*

*52584907711670556013604839586446706324415722155397*

*53697817977846174064955149290862569321978468622482*

*83972241375657056057490261407972968652414535100474*

*82166370484403199890008895243450658541227588666881*

*16427171479924442928230863465674813919123162824586*

*17866458359124566529476545682848912883142607690042*

*24219022671055626321111109370544217506941658960408*

*07198403850962455444362981230987879927244284909188*

*84580156166097919133875499200524063689912560717606*

*05886116467109405077541002256983155200055935729725*

*71636269561882670428252483600823257530420752963450*

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:

XXXX0XXXX

Let’s take another look at our number, clearing out digits within four positions of any zero:

731671765XXXX0XXXX19225119674426574742355349194934

969XXXX0XXXXXXX0XXXX23957XXXX0XXXXXX0XXXX478851843

858XXXX0XXXX12949495XXXX0XXXX95833XXXX0XX0XXXX

XXXX0XXXX4715852XXXX0X0XXXXXXXX0XXXX9522XXXX0XXXX7

668966XXXX0XXXX44523161731XXXX0X0XXXX1121722383113

622298934XXXX0X0XXXX336276614XXXX0XXXX486645238XXX

X0XXXX0XXXXXX0XXXXXXXX0XXXXX0XXXXX0XXXXXXX0XXX0XXXX

0XXXX27121883998XXXX0XXXX274XXXX0XXXXXX0XXX0XXXX6

6572XXXX00X0XXXX78XXXX0XXXXXXX0XXXX2XXXX0XXXX52243

52XXXX0XXXXXX0XXX0XXX0XXXX586XXXX0XXXX415722155397

5369781797784XXXX0XXXX51XXXX0XXXX69321978468622482

8397224137XXXX0XX0XXXX0XXXX0XXXX968652414XXXX00XXXX21XXXX0XXXX0XXXX

XX000XXXX2XXXX0XXXX41227588666881

164271714799244429XXXX0XXXX65674813919123162824586

17866458359124566529476545682848912883XXXX0XXX00XXXX

XXX0XXXXX0XXXX6321XXXX0XXX0XXXXXXX0XXXX6XXXX0X0X

0XXXXX0XXX0XXXX554443629XXXX0XXXX79927244XXXX0XXXX

XXXX0XXXXXX0XXXX9133875XXXX00XXX0XXXX99XXXX0XXXX0X

0XXXX116XXXX0XX0X0XXXXX00XXXXX983XXXX000XXXX5729725

716362695618XXXX0XXXX52XXXX00XXXXXXXX0XX0XXXXXXXX0

Okay, I’ve eliminated all strings of digits whose product will be zero so our new string of digits becomes:

73167176519225119674426574742355349194934969239574788518438581294949595833471852952276689664452316173111217223831136222989343362766144866452382712188399827466572785224352586415722155397536978179778451693219784686224828397224137968652142124122758866688116427171479924442965674813919123162824586178664583591245665294765456828489128836321655444362979927244913387599116983572972571636269561852

(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:

73167176

We would pull out the substrings:

73167

31671

16717

67176

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:

**Original** **Sorted**

73167 77631

31671 76311

16717 77611

67176 77661

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:

99972

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!