A Math Puzzle to Ponder

A very cool math trick from Steven Levitt:

White tells the following story about Quine: Upon hearing that White’s son Steve was not taught multiplication properly due to a switch in school districts, Quine sent him a letter with the following passage:

Since Stevie misses multiplication, he may enjoy gorging on this one. Well, so you have these two numbers, see, and you want to multiply one of them by the other. O. K., so you write them down more or less side by side, as potential headings of two potentially parallel potential columns, roughly thus:

19 27

Then you go to work on the left one, cutting it in half. Write the half underneath. No fractions, though. If it was odd, just forget the fraction. If it was 58 .. 537, just put down 29 .. 268 as its half. That’s near enough. Then, under that in turn, put its half (ignoring, again, the fraction if any); and so on, until you get down to 1. That completes your left-hand column.

19 27
9
4
2
1

Then go to work on the right-hand number, making a column under it by exactly the opposite method: doubling each time. This could go on forever, but don’t let it. Keep your right-hand column lined up with your left-hand column, entry by entry, and stop as soon as you are opposite the bottom of your left-hand column.

19 27
9 54
4 108
2 216
1 432

O. K., so now you have the two columns side by side. The next thing to do is to start in on the right-hand column and cross out a lot of it. Cross out all the entries which have even numbers opposite them in the left-hand column. Keep only those entries in the right-hand column which have odd numbers opposite them in the left-hand column. All right, now add up the right-hand column, what’s left of it after all the crossing out. The result, unless I have made a mistake somewhere, is the answer to your original multiplication problem.

19 27
9 54
4 108 [XXXed out]
2 216 [XXXed out]
1 432
—–
513 [19 * 27 = 513]

It may be that this information reaches Stevie a bit too late to be altogether useful. If I had tipped him off earlier, he would never had [sic] had to learn the multiplication table.

The algorithm actually works, which you will see if you play around with it. And indeed, although certain aspects of the storytelling are played up to make it seem like magic, after a little study it becomes clear (even to someone as mathematically handicapped as I am) why it works. If you like this sort of thing, it is fun to figure out.