The Standard Series

Remember that series of divisibility tests I discussed in the previous essay? Well, I eventually decided that eight tests was the right number, and henceforth I'll refer to that series of tests as the standard series. What I have for you here is some assorted thoughts, partly about products, but mostly about the standard series. I imagine that for both subjects this will be the end of what I have to say.

First, in case you were wondering, I did eventually learn the products all the way up to 2100. Once I'd succeeded, though, I immediately stopped practicing, and immediately forgot everything I'd just learned. The effort wasn't a complete loss, however … recently, when I started practicing again, I was gratified to find that many of the products came back quickly. Maybe if I repeat the whole process a few more times they'll really stick.

In the recent attempt, I discovered a nice technique. Instead of practicing the products all at once, which is a real chore, you can distribute the effort in a pleasing and uniform way by associating each of the seven pages of tableaux with a different day of the week. You can even arrange for the pages to get harder from Monday to Sunday, like the New York Times crossword puzzle! Then, if one day you have a few minutes to kill, you can practice and finish an entire page, and over time all the pages will get equal use.

Earlier, I discovered something completely different, an improvement to the divisibility test based on 899. For the other combined tests, remember, you only had to multiply the thousands digit by something and fold it back into the rest of the number, but for the 899-test you had to change gears and (effectively) divide by 900. However, if you think of 899 not as 900 − 1 but as 1000 − 101, the 899-test becomes just like the others. You can multiply the thousands digit by 101; or even better, you can not multiply at all, and instead just fold the digit back in in two different places.

Consider the same old example, 6877 … in that case you just split off the “6” and think “877 1477 1483”. The result can never be larger than 1908, so if you happen to know the products up to, say, 2100, you're all set; but it's also easy to repeat the process and get 584, same as with the old method. (So, the improvement isn't that we got rid of the division by 900, it's that we found a better way to do it; and, ironically, the better way is based on a principle that we were already using.)

As it happens, I have a pretty good idea of what led to the improvement. It probably helped that I'd read the (fascinating) article The Art of Mental Calculation, with its explanation of how one can divide by 59 by dividing by 60 and feeding the quotient back into the dividend, but the real cause was that as part of a very pleasant and extended correspondence, I'd learned about a new class of divisibility test. (So, the following is also a footnote to the essay Other Methods.)

The original sources (Divisibility Tests and Divisibility Rules) don't have the words to say so, but the new divisibility tests are similar to reduction rules. Instead of a number of the form 10^k ± A, you use a number of the form A×10^k ± 1, typically with k = 1; and instead of from left to right, you work from right to left; but the rest is the same. (By the way, as I mentioned in Operations, I think left to right is better.)

If, for example, you want to test divisibility by 13, you can use the rule based on the number 39: split off the last digit (k = 1), multiply it by 4 (A), and add it back into the rest of the number (the minus sign). To see why that works, suppose we split off the last digit algebraically, and write the original number in the form c×10 + d. Then we can add 39d, a multiple of 13, without affecting divisibility.

(c×10 + d) + 39d = c×10 + d×40 = (c + 4d) × 10

But, the factor of 10 doesn't affect divisibility either, so we can drop it, leaving c + 4d … which is exactly what the rule computes! (Unfortunately, the factor of 10 does affect congruence, so you can't use the rule to compute n mod m.)

Alternatively, you can use the rule based on 91: multiply the last digit by 9 and subtract it from the rest of the number. That may not sound as nice as the first rule, but as my correspondent pointed out, there's another way to implement it. Instead of multiplying by 9 and subtracting, you can just subtract from the tens place and add to the ones … and there you have the double-feedback idea that led me to the improvement in the 899-test.

So, anyway, now I can present the standard series of divisibility tests as a simple table. The first column shows the number you multiply the thousands digit by; the second shows the list of prime factors you look for in the result.

−1	7 11 13
−3	17 59
−7	19 53
+11	23 43
+101	29 31
+1	37
n/a	41
n/a	47

Two notes:

• The double-feedback idea applies to the fourth row as well as the fifth.
• The improvement to the 899-test also fixes a small problem. It takes a tiny but noticeable effort for me to split off the thousands digit and form concepts of it and the rest of the number as distinct entities; and as it turns out, I can't maintain those concepts and also divide by 900. So, before, I was always tempted to skip ahead and check the sixth row before the fifth, just so I wouldn't have to split the number again.

One thing about the standard series that I see I haven't mentioned is that it's feasible and useful even for five- and six-digit numbers. First, it's feasible … you have to split off a thousands part, not just a thousands digit, and you have to be able to multiply it by 3 and by 7, but that's not too hard, and the rest is just addition and subtraction. One detail that doesn't crop up very often with four-digit numbers is that the multiplied thousands part may be larger than the rest of the number, in which case it's convenient to change sign and subtract the other way 'round. (That doesn't affect divisibility.) For example, if you apply the third test to 123457, you'll end up trying to take 861 from 457.

As for being useful, well, of course given an arbitrary composite number you may not be able to factor it. However, the odds aren't bad … the standard series can find a factor almost exactly half of the time (49.8%). (And, that's just the theoretical limiting value … for four-digit numbers, the odds go all the way up to 52.0%!) Here are the actual counts, excluding numbers with factors of 2, 3, or 5.

number of digits	4	5	6
composite, hit	1248	11930	119467
composite, miss	91	3707	51627
prime	1061	8363	68906
prime odds	92.1%	69.3%	57.2%

The last row shows a different set of odds, the odds that a number is prime given that you've run through the series and found no factor. So, even if you don't get a factor, you do get some information … fairly good information in the four-digit case, not so good in the other cases. (For seven-digit and larger numbers, by the way, the odds switch to favor compositeness.)

Finally, just to end with something fun, here's a little commutative diagram.

901	1003
17 × 53	17 × 59
1007	1121
19 × 53	19 × 59

It's also a little multiplication table! I like to think of such diagrams for various numbers, for various reasons … {29,31} × {59,61} is also nice, for example. They've never helped me remember anything, but I like them anyway.