#WeHateMath Project Euler 8 – Math Makes Everything Better

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!

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