Game time! Pick a small number, say 20. Now split 20 into as many additive factors as you want.

Note: By additive factor, I mean two numbers that add up to give your original number. Example: 13 + 7 = 20. Therefore, 13 and 7 are additive factors of 20.

The goal of this game is to split up the number, say 20, in such a way that when you multiply the additive factors together you get the biggest number possible.

So let’s give it a try with 20. Take 20 and split it up into 10 and 10. This is legal since 10 + 10 = 20. And 10 * 10 = 100. Not a bad first attempt.

Now let’s try splitting the 20 even more, say 5, 5, 5, 5. Since 5 * 5 * 5 * 5 = 625, we have improved our result.

Let’s split even further! How about twenty 1’s. Then 1 * 1 * 1 … * 1 = 1. Hey wait a minute, splitting up the 20 at first gave us a bigger product, but when we split too far we ended up with just 1. Hmm, this problems looks like it is going to need some further investigation.

We are going to do a case-by-case analysis. Say you start with a 1, clearly 1 cannot be broken up at all, so it just stays as a 1.

How about 2? Well if we break up the 2 into 1 and 1, but 1 * 1 = 1. We would be better off just leaving it as a 2. Therefore, 2 just stays as 2.

How about 3? We could break 3 up into 2 and 1, but 2 * 1 = 2. We would be better off just leaving it as a 3. Therefore, 3 just stays as 3.

How about 4? We could break 4 up into 2 and 2, and 2 * 2 = 4. It doesn’t matter if we break up a 4 or not since 4 = 4. I chose to break up 4 into two 2’s because it will look prettier later on.

How about 5? This is where it gets tricky. A 5 could be broken up in a lot of different ways. However, after much wasted loose leaf, it is clear that the best way to break up a 5 is into a 2 and 3, and 2 * 3 = 6. Since 2 and 3 just stay as a 2 and 3, this is as far as a 5 can be broken up.

How about 6? Again, some effort is involved, but a 6 should be broken up into 3 and 3, and 3 * 3 = 9.

Ok, 7 is where things get interesting. Since 3 seems like a good number let’s for sure break up the 7 into a 3 and a 4, and 3 * 4 = 12. However, we already know that every 4 should be broken up into two 2’s. So 7 really breaks up into 3, 2, 2.

This trend continues with 8. Again, 3 is a good number so let’s break up 8 into 3 and 5. But 5 breaks up into 2 and 3. So 8 is really just 3, 3, 2, and 3 * 3 * 2 = 18.

Here is a table of what we have discovered so far and the next few numbers with the optimum way to decompose them and their product

 Number Decomposition Product 1 1 1 2 2 2 3 3 3 4 2,2 4 5 2,3 6 6 3,3 9 7 2,2,3 12 8 2,3,3 18 9 3,3,3 27 10 2,2,3,3 36 11 2,3,3,3 54 12 3,3,3,3 81 13 2,2,3,3,3 108 14 2,3,3,3,3 162 15 3,3,3,3,3 243 16 2,2,3,3,3,3 324 17 2,3,3,3,3,3 486 18 3,3,3,3,3,3 729 19 2,2,3,3,3,3,3 972 20 2,3,3,3,3,3,3 1458

Well that is quite unexpected! If we properly decompose 20, we get 2, 3, 3, 3, 3, 3, 3 which gives a product of 1458, much larger than our first attempt of 100!

I just want to dwell on the process of how we broke down each number a little further.

First, we realized when we did a case by case study in the early numbers that 2 and 3 should not be broken up any further; they are the smallest possible number we want.

Second, we realized that for bigger numbers like 5, 6 and 7, it was best to split off a 3 at first and then work with what was left.

Third, we also realized that a 4 should NOT be broken up into a 3 and 1, since 3 * 1 = 3 and 3 is less than 4. One way of thinking about this is we want to split off a 3 from the number, but ONLY if it does not leave us with a 1. Since multiplying by 1 does not increase our product at all.

So let’s make that our process.

Step 1: Is the number a 2 or 3? If so, we are done, do not split the number up any further.

Step 2: Is the number a 4? If so, break it up into a 2 and a 2.

Step 3: Is the number bigger than a 4? If so, break off a 3. Then repeat Step 1.

Here is a picture of how this process works for a medium sized number, say 16:

So from the diagram above, a 16 breaks up into 2,2,3,3,3,3 which is the same result we obtained from the table.

One last thing, the process we described above is called a recursive algorithm. Many of you may not understand what that means, but at least now you can sound cool at your next party when you say “ya, I sometimes fool around with recursive algorithms on the weekend, no big deal.”