#WeHateMath Project Euler 11 – Largest Product in a Grid

In the 20 X 20 grid below, four numbers along a diagonal line have been marked in red.

Euler11a

The product of these numbers is 26 63 78 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 2020 grid?

 

Yikes.

This is the first Project Euler problem that has personally offended me. That may seem strange but it’s because this is at it’s core an arithmetic problem, not math. At first glance, it seems similar to Euler problem 8, but it’s really a brute-force, grind-out-every-product-and-compare-them, ugly, arithmetic problem. So while I would have preferred a more elegant solution (a scalpel instead of a hammer, as it were), I went with the ugly one.

The perfect programming language for ugly, brute-force hammer solutions is C, so that’s what I used. (I considered Fortran, which is actually better for brute-force math and arithmetic problems but the last time I used it was in 1977).

So when I ground out the answer, here’s what I got:

MacPro15:WeHateMath tsinclair$ time ./Project_Euler11
70600674

real0m0.003s
user0m0.001s
sys0m0.001s

So it only took about 3-thousandths of a second to get my answer, but I’m still annoyed.

#WeHateMath Project Euler 10 – Summation of Primes

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

We’ve spoken about primes before but this problem is different. First of all, it seems pretty straightforward. We’re adding up a list of numbers. Granted, we have to generate the list of numbers first but generating a list of primes is not unknown technology. (Like any nerd, I let a computer do the hard work).

The question is (as it is with all of these problems), why do it?  What’s the point? That’s what I had to ponder for a while. So I decided to let my computer grind through a few possibilities. Using a combination of a spreadsheet and some computer code (and there’s no reasonable way to do this without some programming skills), I poked at some numbers.

One of the first things I discovered was that (no surprise) the sums get big pretty quickly. I started by asking Wolfram Alpha to do prime sums for me. It worked fine for 10, 100, 1000 and up to 1000000. But when I asked for the sum of primes less than 2,000,000 it crapped out on me. You see, Wolfram Alpha has built-in limits on how much processing time you can use.

Okay, you have my interest now.

I poked around and found some program code that did sums of primes, loaded it into XCode, compiled and ran it. At first I used it to check the numbers that Wolfram Alpha had given me (no harm in checking). Of course, as the numbers got bigger, the processing took longer and longer. I decided to shorten things by asking for the sum of primes between 1,000,000 and 2,000,000 (since I already had the sum for 1,000,000). I dumped it into my spreadsheet and made a table:

 

N

Sum of Primes

Sum of N

Diff(N, Sum_of_Primes)

Diff(N, Sum_of_N)

10

17.00

55.00

7.00

45.00

100

1,060.00

5,050.00

960.00

4,950.00

1000

76,127.00

500,500.00

75,127.00

499,500.00

10000

5,736,396.00

50,005,000.00

5,726,396.00

49,995,000.00

100000

454,396,537.00

5,000,050,000.00

454,296,537.00

4,999,950,000.00

200000

1,709,600,813.00

20,000,100,000.00

1,709,400,813.00

19,999,900,000.00

1000000

37,550,402,023.00

500,000,500,000.00

37,549,402,023.00

499,999,500,000.00

2000000

142,913,828,922.00

2,000,001,000,000.00

142,911,828,922.00

1,999,999,000,000.00

 

Just for fun, I added a column of straightforward sums plus differences. (You never know what relationships will pop up.) I also ran my prime summing program with a timer and here are the results:

 

Enter min range: 2
Enter max range: 2000000
Sum of prime numbers is: 142913828922
real19m57.296s
user19m42.095s
sys0m0.625s

 

In human-speak, this means that the calculation took almost twenty minutes of ‘real’ time (as in wall-clock time) and about two-thirds of a second of computing time. Just out of curiosity, I ran the same program but just for the primes between one million and two million:

 

Enter min range: 1000000
Enter max range: 2000000
Sum of prime numbers is: 105363426899
real14m20.074s
user14m9.366s
sys0m0.195s

 

Interestingly enough, it took almost the same amount of ‘real’ time but about a third of the computing time. Just for fun, I wondered how much time it would take to do sum of primes up to 1 million:

 

Enter min range: 2
Enter max range: 1000000
Sum of prime numbers is: 37550402023
real5m15.445s
user5m7.393s
sys0m0.213s

 

Well, about one-third of ‘real’ time and a bit more computing time. The latter was to be expected but the former isn’t.

In any event, I’m still not sure about the point to this problem. If I figure it out, I’ll post an update.

#WeHateMath Project Euler 9 – Pythagorean Triplets

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Let’s get the problem part out of the way first. It turns out to be pretty easy to generate Pythagorean Triplets (sometimes called Pythagorean triples):

Pick two positive integers, m and n, ,where m < n. Generate your three values like so:

Of course, doing this by hand is annoying and this is just the sort of thing for which spreadsheets were made. I set up the formulas and then starting fiddling with values of m and n and it just took a few tries to range in on the answer:

m

5

n

20

a

375

b

200

c

425

Sum(a,b,c)

1,000

Product(a,b,c)

31,875,000

a^2

140,625

b^2

40,000

a^2 plus b^2

180,625

c^2

180,625

Readers know by now that the point of the Project Euler posts is not to simply get the answer to the problem but to figure out the point of the problem. In this case, that’s not obvious. Though Pythagorean Triples are a surprisingly hot topic of discussion among mathematicians if my casual research is anything to go by. I even found a paper documenting a new way to generate triples that suggests an interesting application of the math to cryptology. It’s especially surprising when you consider that these triples have been around for over 2000 years.

The classic Pythagorean triples are (3, 4, 5) and (5, 12, 13). You can generate new triples by using multiples of each element. In our answer above, (375, 200, 425) is a multiple of (3, 4, 5). There are others, however. For example (4, 3, 5) is also a valid triplet but can’t be generated by the traditional methods.

Pythagorean Triples are connected to both Fibonacci numbers and primes, which we’ve discussed previously.. The two classic triples each have Fibonacci values as two of the three values. In addition, up to two of the legs can be prime numbers but because at least one of the legs must be even, there is no triple where all three elements are primes.

This is a great example of pure mathematics that may (or may not) someday find some practical application. I view mathematics as a way to perform experiments on the universe, but unlike traditional laboratory science, my lab bench is conveniently located between my ears. So the next time someone tells you that studying math is impractical, remind them:


#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!

Project Euler #7 – Prime Mysteries of the Mind

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10,001st prime number?

“Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate.”

Leonard Euler, in G. Simmons, Calculus Gems, McGraw-Hill, New York, 1992

According to Wolfram Alpha, the 10,001st prime number is 104,743. Now (as always) we must ask,“what’s the point?”

To be fair, it’s all well and good that we have these fancy computers that we can just ask for the answer, but let’s dig deeper and get more background on what’s so hot about prime numbers. As the quote above from noted brainiac Leonard Euler indicates, prime numbers are a mystery wrapped in an enigma covered in secret sauce.

We’ve talked about prime numbers before and how they’re used to secure the Internet. But the ancient Greeks studied primes and they didn’t even have smartphones (at least, I don’t think so….nope, they didn’t). One thing to note about primes is that they are devilishly hard to predict. I mean, if I gave you a sequence of even numbers and asked you to determine what the next number in series would be, that would be a no-brainer. However, if I gave you a sequence of prime numbers, that would involve a lot more work. Factoring numbers (our main test for primality) is one of those problems that are known as NP (Non-Polynomial). In plain talk, there are no shortcuts to the answer. But what if we asked the question a different way?

That’s what a man named Eratosthenes did. Prime numbers were as weirdly fascinating to the ancient Greeks as they are to us and Eratosthenes was a noted mathematician of the day. Just to give you a sense of the man, he was also a music theorist, poet, astronomer, invented geography and in his spare time was the chief librarian of the greatest collection of ancient wisdom of his times, the Library at Alexandria, not to mention being the first person to calculate the circumference of the ENTIRE FREAKING PLANET.

Frankly, it’s all I can do to get through my daily Twitter feed before I feel the need for a lie down. But I digress.

Anyway, while his fellow mathematicians were mapping out primes the hard way, Eratosthenes asked the question, “How do we find the prime numbers in a given sequence of numbers?”. One day he had a revelation. He already knew how to find if a number was prime the hard way. But, he reasoned, any multiple of a prime is by definition not prime.
Here’s how it worked. Consider the first ten digits (1 is crossed off since it is neither prime or non-prime).

X 2 3 4 5 6 7 8 9 10

Our first prime is 2, so we cross off all multiples of 2.

X 2 3 X 5 X 7 X 9 X

3 is also a prime, so we cross off all multiples of 3.

X 2 3 X 5 7 X X X

We’ve finished the sequence and all we have left are the primes 2, 3, 5 and 7. We can do this for any sequence of numbers, filtering out the primes like grains of sand through a sieve. Hence the name for this technique, which has survived to this day – the Sieve of Eratosthenes. As a side benefit, this reduces the effort of finding primes to simple arithmetic, making it perfect for handing off to a machine. (In fact, one of the first programming problems they give students is to code up their version of the Sieve.)

One more thought about primes and this one’s a bit more relevant to the Project Euler problem above. If we map out the Nth primes for N in {1, 11, 101, 1001 and 10,001}, we get:

N

Gap

Nth Prime

Gap

1

n/a

2

n/a

11

10

31

29

101

90

547

516

1001

900

7,927

6,926

10001

9,000

104,743

96,816

If we look at the gaps we can see that, as the sequence numbers get bigger, the gaps between primes get bigger. It’s even more obvious when we graph out the first 100 primes:

This actually makes intuitive sense. Larger numbers have more possible factors so are less likely to be prime. (Give that a moment to sink in.) This is an illustration of what is known as the prime number theorem. Here’s the idea:

  • Pick a large positive integer. Call it N.

  • Pick a random integer between 1 and N. Call it R.

The probability of R being random are roughly 1/ln(N). (one divided by the natural logarithm of N). So the bigger N is, the smaller the odds of R being prime. In other words, as we see in our graph above, the gaps between prime numbers get bigger as our numbers get bigger. Like people, prime numbers are easier to understand when we look at them in groups.

“Some order begins to emerge from this chaos when the primes are considered not in their individuality but in the aggregate; one considers the social statistics of the primes and not the eccentricities of the individuals.”

P.J. Davis and R. Hersh, The Mathematical Experience, Chapter 5

 

Project Euler #6 – Hip to be Square

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

I’m very well acquainted too with matters mathematical,

I understand equations, both the simple and quadratical,

About binomial theorem I’m teeming with a lot of news–

With many cheerful facts about the square of the hypotenuse.

Gilbert & Sullivan, “The Pirates of Penzance”

At first glance this seems to be just arithmetic which is kind of insulting. As we’ve discussed, arithmetic is only about getting to an answer and that’s the kind of boring stuff that is only fit for machine work. Clearly there must be something else going on here or I’m just going to be terribly annoyed. So let’s take a look at the math (which is much more interesting) behind sum of squares and then see if we can figure out a cunning way of getting our answer without all of that boring arithmetic. It turns out that there are at least two interesting things about the sum of squares.

The most interesting (to me, at least, dork that I am) has to do with storing cannonballs.

Let me explain.

Imagine you’re on vacation and you visit an historical site and you come across a cannon, complete with ammunition:

Photo courtesy of Hans Braxmeier (via Pixabay)

Pretty standard stuff, but what if you wanted to figure out how many cannonballs are in that pile? Better still, could you do it without actually counting any cannonballs? It turns out that you can. Note that the top of the pile has one cannonball, the layer underneath has four and so on. In other words, if we count the layers from the top down, our four layer pile here has:

12 + 22 +32 + 42 or 30 cannonballs (1 + 4 + 9 + 16). In other words, our pile of cannonballs can be expressed as a sum of squares. So we don’t need X-ray vision, we just count the number of layers in the pile and do a little arithmetic. Not bad! Note that this only works if the pile is in the shape of a square based pyramid, hence the name square pyramidal numbers for the number sequence. Of course, if there was an easy way to calculate the sum of squares than by doing all that boring arithmetic that would be better but we’ll talk more about that in a bit.

Okay, let’s look at an example that’s a bit more real world and not so much ‘Battle of Liechtenstein’. Sum of squares is more often used in statistics to analyze a set of data points. First let’s get the boring arithmetic over with so we can get on with our lives. Fortunately I recently learned about a programming language called Haskell that lets me do stuff like this pretty easily.

let x = sum(map (^2) [1..100]) (sum of squares of 1 to 100)
print x
338350
let y = foldl (+) 0 [1..100] (sum of 1 to 100)
print y
5050
[5050^2]
25502500 (square of the sum of 1 to 100)

When mathematician Carl Friedrich Gauss was eight years old (in 1785, by the way), his teacher asked the class to give the sum of the numbers 1 to 100. The idea was to keep the little buggers busy and quiet for at least a few minutes but Carl piped up almost immediately with the answer 5050. Not only did he do the sum in his head, he was able to prove his answer was correct.

Here’s how he did it (in his head, by the way):

Picture the numbers 1 to 100 in a line:

1 2 3 4 5 6 7 … 100

Now picture another row, with the same digits arranged in the opposite order:

100 … 7 6 5 4 3 2 1

Add the two rows together:

1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101 ...

Since there are 100 pairs of numbers, each adding up to 101, then the total sum is 101 x 100 or 10100. But the sum of the original sequence (which is what we wanted all along) is half of that or 5050. Sometimes you don’t need a computer if you look at the problem creatively enough.

So it turns out that the sum of the first n natural numbers (for any n) is:

Let’s apply that to our first 100 numbers and see if we really needed to write a computer program to sum 1 to 1000. Plugging 100 in for n we get (100(100 + 1))/2 or 5050.

So is there an easy way to get the sum of squares? It turns out that there is indeed:

Okay so the sum of the squares of 1 to 100 is 338,350 and the square of the sums is 25,502,500. The difference, therefore, is 25,164,150. At this point one could realistically ask, “So what?” (and who could blame you?)

It turns out that the sum of squares is an important technique in statistics for determining sample variance. That is to say, the amount that a set of data numbers varies from the average value. The bigger the variance, the more likely you’re going to have go back to the old drawing board and re-think your experiment. The traditional way to calculate variance is:

  • Find the average (mean) of the sample numbers.

  • Subtract each value from the mean and square the difference.

  • Add up all of the squared differences.

So if all of your data were perfect then the differences from the mean would be zero, which sums up to a total variance of zero. Such is the way of a perfect world. But the more your actual data points vary (see what I did there?), the bigger the difference from the mean and the bigger your variance.

That’s all well and good but where am I going with this? It turns out that there’s a shortcut way to get sample variance:

  • Sum up your sample data values and square the sum

  • Sum the squares of your sample data

  • Subtract the square of the sum from the sum of the squares

  • Divide by the number of data values

You don’t have to calculate the mean or the squares of the differences from the mean AND we’re back to our original technique of subtracting the square of sums from the sum of the squares. As your sample size gets bigger, this saves us a TON of work.

Thus endeth the lesson….

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.