Four Digits

After I learned the three-digit products, I was satisfied for a while, but eventually I started noticing some things that made me want to learn even more products.

Actually, I'd noticed one of the things as soon as I started walking around happily factoring numbers. Street addresses often have four digits, but they also often end in 0 or 5. In the first case, of course, all you have to do is factor the first three digits and then throw in extra factors of 2 and 5, but in the second case, it's not so easy. Sure, you can remove a factor of 5, but the result isn't necessarily a three-digit number. To be able to factor all such addresses, you'd need to know the products up to 2000.

Another way to understand why the number 2000 is a significant boundary is to think in terms of multiplication. When you learn a product, you become able to factor not only the number itself but also any multiple of the number that involves only factors of 2, 3, and 5. So, as far as factoring four-digit numbers is concerned, learning a product below 2000 is at least five times as useful as learning a product near 10000.

More generally, for any number D (up to 9), the number 10000/D is a significant boundary.

Speaking of boundaries, another thing that nagged at me was that 1000 wasn't a page boundary, or even a column or tableau boundary. So, I was tempted to learn the products up to 1050, or maybe 1200.

The thing that finally tore it, though, was my digital clock. If I'd been factoring any numbers during the day, it would just drive me crazy to be lying in bed at night staring at some number like 11:47 and not immediately knowing all its factors. (In case you're wondering, yes, I was, and am, keenly aware that it's incorrect to read 11:47 as decimal 1147 … I ought to see it as a number in base 60. What can I say? The digits are right there, and I already group four-digit numbers in pairs internally … for example, I think of 6877 not as “six thousand eight hundred and seventy-seven” but as “sixty-eight seventy-seven”.)

Anyway, I decided I had to learn the products up to 1260. Then, once I'd gotten started, and had a feel for how easy it was, I decided I might as well continue past the D=7 boundary up to the page boundary at 1500. And so I did … in fact I finished just a few days ago. In all, I learned 63 products on top of the hundred I already knew.

I imagine some day I might learn the products up to 2100. That would cover both the street addresses and the D=5 boundary, and also take care of all the year numbers I'm likely to see. And, the previous effort brought me within striking distance … I'd only need to learn 82 more products. Beyond that, there are a few other points of interest, but none of them are very compelling, and I doubt I'd bother extending the range any further.

Except … there is one other point of interest, one that's extremely compelling but almost impossible to attain … the grail of products. If I were to learn all the four-digit products, I'd be able to factor almost any number, almost instantly. In everyday life one sees lots of three-digit numbers, and plenty of four-digit numbers, but hardly any numbers with five or more digits, because such a large string of digits is usually broken into groups for readability. (ZIP codes are an exception, but an easily handled one, since one mostly sees the same codes over and over. UPC numbers are an exception, too, but who pays attention to those?) The difficulty, of course, is that there are a lot of four-digit products … 1339 of them, in fact, including the ones I've already learned. And, that's too many, even for me, except perhaps as a multi-year hobby.

Since I realized that, I've been puzzling over the problem. Is there any good way to factor four-digit numbers quickly? The method of products requires too much memorization, and the standard method takes too long, but perhaps there's some intermediate method, or combination of methods, that would yield adequate speed without too much work? I haven't solved the problem yet, but I do have a few thoughts.

One early thought I had was that I could learn the value of 1000 mod p for all the relevant primes p, and then test divisibility by folding the thousands digit into the rest of the number and factoring the result. Unfortunately, that doesn't really help. I can factor a three-digit number about as quickly as I can perform a standard divisibility test … which is great if I have a single three-digit number, but not so great if I have a different three-digit number for every prime p.

But, the thought wasn't a complete waste, because later I realized I wouldn't have a different three-digit number for every prime p … there are some cases in which 1000 mod p has the same value for different primes. In particular, it has the value −1 for the primes 7, 11, and 13. So, I can test divisibility for all three primes at once, by folding the thousands digit, factoring, and then checking for factors of 7, 11, or 13.

That's probably a bit abstract, so let's look at an example. (The congruence here is modulo any or all of the three primes.)

6877 = 6 × 1000 + 877 ≡ 877 − 6 = 871 = 13 × 67

Since the right side is divisible by 13, so is the left. We still have to divide 6877 by 13 and factor the result, but at least the hard part, finding one factor, is done.

6877 = 13 × 529 = 13 × 23²

By the way, now you can see why the D=7 boundary is interesting. If I find a factor of 7, and divide, I might still have a four-digit number, but it's certain to be a number I can factor immediately.

There are many little points that are worth noting.

• Normally, when you're factoring a number, you have to keep track of any factors of 2, 3, and 5 you remove. For the folded number, though, you don't, because you're only interested in factors of 7, 11, and 13. I think of the simplified process as “pseudo-factoring”.
• Since the basic operations take about the same amount of time, replacing three divisibility tests with one factorization gives roughly a threefold increase in speed. That's not huge, but it's certainly better than nothing.
• Using the combined divisibility test to recognize numbers with factors of 7, 11, and 13 takes care of 673 of the 1339 four-digit products, leaving 666. That's still too many, I think, but it's an improvement.

The main little point, though, is that up 'til now I've avoided mentioning the reason that 1000 mod p has the same value for the three primes.

1001 = 7 × 11 × 13

Yes, it's that same old number again. But, think about it for a minute … the first three primes (2, 3, and 5) have simple divisibility tests, and then the next three (7, 11, and 13) happen to multiply together just so, so that a single combined divisibility test is possible. How unlikely is that?! (That's not entirely a rhetorical question … see In Other Bases.)

Anyway, from that perspective, the next step is clear. Instead of messing around with values of 1000 mod p, we should just look for numbers near 1000 that have more than one large prime factor. (Here it's helpful to know the products up to 1050.) There aren't any more numbers that have three such factors, but there are some that have two.

1003 =	17 × 59
1007 =	19 × 53
989 =	23 × 43

That gives three more combined divisibility tests. In the notation from Divisibility, the tests are of the form {3,d}, with large values of d; amusingly, in that essay I dismissed such tests as not useful. The difference is, here d is only multiplied by a single digit, so it doesn't matter if it's large.

The tests should be performed in the order shown, i.e., in descending order by success probability. If you do that, the tests catch 132, 118, and 107 products, respectively, leaving 309.

After that, it's not entirely clear what the next step should be. For what it's worth, here are two tests I've been using that take care of the next three smallest primes.

899 =	29 × 31
999 =	33 × 37

The second test doesn't produce much of an increase in speed, since it only replaces one standard divisibility test, but it's hard to resist, just because the folding step is so easy.

The first test is somewhat peculiar. Instead of folding the first digit, you have to look at the first two digits and remove the largest possible multiple of 9. Here's how it works for that number we looked at earlier.

6877 = 7 × 900 + 577 ≡ 577 + 7 = 584 = 2³ × 73

Since the right side isn't divisible by 29 or 31, neither is the left. (Of course we knew that already.)

Those two tests catch 106 and 43 products, leaving 160.

At this point, I don't know anything else to do except go back to the standard method of testing primality. Any composite number less than 10000 must be divisible by a prime less than 100, and we've already taken care of all the primes below 41, as well as 43, 53, and 59, so there are ten primes left to check.

41 47   61 67   71 73 79   83 89   97

The first two primes are significantly smaller than the rest. If we perform standard divisibility tests for them, that takes care of 38 and 31 more products, leaving 91.

(Now is probably a good time to point out that a standard divisibility test doesn't have to use long division. My current preferred method is backward modulation.)

After that, we can perform more standard tests, but there's no other obvious stopping point. So, here's the list of product counts for the remaining primes.

21 17   15 12 9   8 6   3

Now let's step back and see what we've learned. If we want to factor four-digit numbers, there's a fairly well determined series of divisibility tests we can use, some combined, some standard; and the more tests we use, the fewer products we have to know. (Just for comparison, the standard method requires 22 tests.)

tests	products
0	1339
1	666
4	309
6	160
8	91
12	26
16	0

Unfortunately, none of the possibilities appeals to me. I might be willing to learn a hundred products to be able to factor four-digit numbers almost instantly, but for me “almost instantly” doesn't include any method that requires more than one test. The only consolation I can see is that the products accumulate. If you learn the following three products, for example, you don't have to test for divisibility by 97, and then you can gradually learn more products from there.

	97	101	103
97	9409	9797	9991

If I could get down to eight tests, that would be pretty good.

Or … if you decide in advance on the number of tests you want to use, you can tackle the products from the smallest number upward instead of from the largest prime downward. Suppose, for example, that you've decided to use eight tests. Even if you don't learn any products, you can factor everything up to 61² = 3721; and if you can be bothered to learn eight products, you can factor everything up to the D=2 boundary at 5000.

	61	67	71	73	79
61	3721	4087	4331	4453	4819
67	-	4489	4757	4891	.

Recently I had one more worthwhile thought: instead of products, one could memorize “half-products”, i.e., memorize just the smaller of the two prime factors. In theory that might save half the effort, or even more than half, since I have better associative hooks for smaller primes. On the other hand, there are some disadvantages as well, which I won't go into.

So, anyway, that's where I've gotten to in my thinking.