In Other Bases

It didn't take me long to realize that the question, as stated above, isn't productive. If you take the product of the second three primes, subtract one, and take the cube root, you get the number we know as 10, no matter what base you're in. So, yes, base 10 is unique in that sense. But, there are other senses that are just as plausible. For example, the number 1001 in base 12 is the product of the fourth, sixth, and eighth primes … in decimal,

1729 = 7 × 13 × 19.

And, who's to say if that's better or worse?

What we need to do, it turns out, is step back and remember the reason 1001 is interesting, which is that it yields a simple divisibility test for any and all of its prime factors. Then, instead of asking which primes are factors of 1001, we can ask which primes have simple divisibility tests.

That, of course, begs the question of what counts as simple. I'll come back to that later; for now, you're stuck with my arbitrary decision that there are seven simple divisibility tests.

test	sign	digits	mnemonic	incl.	number	factors
D	0	1	last Digit		10
S	+1	1	Symmetric sum		1#
A	−1	1	Alternating sum		11
2	+1	2		S,A	10#	= 1# × 11
2	−1	2			101
3	+1	3		S	100#	= 1# × 111
3	−1	3		A	1001	= 11 × 1#1

In the last two columns, I've used the hash mark as the digit that represents −1, an idea I mentioned at the end of Fractions in Base 2. I'll come back to that, too. But, just as a quick example, in base 10 the number 100# has the same value as the number 999.

Now, here's a huge table that shows which primes have simple divisibility tests. For primes up to 19, the table also shows the simplest test that applies to the prime. The score in the last column is another thing I'm going to come back to.

base	2	3	5	7	11	13	17	19	other		score
2	D	A	2	3	-	-	-	-			0.0
3	S	D	2	3	-	3	-	-			7.7
4	D	S	A	3	-	3	2	-			13.1
5	S	A	D	3	-	2	-	-	31		10.7
6	D	D	S	A	-	-	-	-	31 37 43		8.0
7	S	S	2	D	-	-	-	3	43		7.5
8	D	A	2	S	-	2	-	3	73		13.7
9	S	D	A	3	-	3	-	-	41 73		11.2
10	D	S	D	3	A	3	-	-	37	101	19.2
11	S	A	S	3	D	-	-	3	37 61		17.6
12	D	D	2	3	S	A	-	3	29	157	23.7
13	S	S	2	A	-	D	2	-	61	157	15.1
14	D	A	A	D	-	S	-	-	61	197 211	10.1
15	S	D	D	S	-	-	-	-		113 211 241	1.8
16	D	S	S	3	-	3	A	-		241 257	13.8
17	S	A	2	3	-	3	D	-	29	307	16.4
18	D	D	2	3	-	2	S	A		307	18.0
19	S	S	A	3	-	-	-	D		127 181	6.5
20	D	A	D	A	-	-	-	S		127 401 421	6.5
21	S	D	S	D	A	2	2	-		421 463	21.4
22	D	S	2	S	D	3	-	-	23 97	463	20.7
23	S	A	2	3	S	3	-	-	23 53 79		22.2
24	D	D	A	3	-	-	-	-	23 79	577 601	5.9
25	S	S	D	3	-	A	-	-	31	313 601	11.1
26	D	A	S	3	-	D	-	3	31 37	677	17.8
27	S	D	2	A	-	S	-	3	37 73	757	16.2
28	D	S	2	D	-	-	-	-	29	157 271 757	4.5
29	S	A	A	S	-	3	-	-	29 67	271 421	12.7
30	D	D	D	3	-	3	2	3	29 31 53 67		25.7
31	S	S	S	3	-	2	-	3	31 37	331	17.9
32	D	A	2	3	A	-	-	-	31 41	151 331	15.0
33	S	D	2	3	D	-	A	-		109 151 1123	15.9
34	D	S	A	A	S	2	D	-	89	397 1123	22.2
35	S	A	D	D	-	3	S	-	97	397 613	14.4
36	D	D	S	S	-	3	-	-	31 37 43 97	1297	16.0
60	D	D	D	3	-	2	-	-	59 61	277 523 3541	11.3

I stopped at base 36 because that's the largest base with only numbers and letters as digit symbols (for another example of that, see Expansion Calculator), but then I added base 60 because I've talked about it before.

Now we can start answering questions … which bases, for example, have simple divisibility tests for the first six primes? There's base 10, of course, and there's base 12, and then there are four more that I'll dismiss because they're too gnarly: bases 21, 22, 23, and 34.

What about base 12, though? How does it compare to base 10? Well, after the first six primes, base 12 has three more simple divisibility tests, for 19, 29, and 157, while base 10 has only two, for 37 and 101. So, if we're concerned with the number of testable primes, base 12 is better. If, however, we're concerned with the number of tests, base 10 actually has an advantage. Suppose we want to test every one of the first six primes.

• In base 10, we can look at the last digit to test 2 and 5, add up the digits to test 3, then use the 3-test to take care of 7, 11, and 13. So, we have to do one trivial test, one easy test, and one hard test.
• In base 12, the process is almost the same, but not quite. We can look at the last digit to test 2 and 3, add up the digits to test 11, and use the 3-test to take care of 7 and 13 (and 19), but then we have to do a second hard test to check for 5 (and 29).

At this point, you may be wondering why I'm fixated on the first six primes. In base 12 we can still get six primes with three tests, just not the first six; isn't that just as good? Well, no, actually. If, as is often the case, you're trying to factor a number, then the smaller the prime, the more productive it is to test for it. Here, for example, the base-10 test for 5 will factor one in five numbers, or 20%; the base-12 test for 19, only 5.3%.

That last thought leads to a better way to compare bases: instead of arbitrarily looking at the first six primes, we should look at the probability of factoring a random number with a simple divisibility test … and that brings us back to the score. The score is exactly that, the probability of factoring a random number, except it's expressed as a percentage, and doesn't count factors of 2, 3, 5, and 7, since there are always simple tests for those. (If you want the full probability, you can just divide by 4.375 and add 77.1.)

By the way, although I didn't think of it until too late, this would have been an excellent place to use risks instead of probabilities. The probabilities for the different primes combine awkwardly by inversion and multiplication, but the risks just add up. The risk of being divisible by 19, for example, is 0.054.

Anyway, now we can compare the bases by score. I marked in bold the ones that are at least as good as base 10, and, guess what, with one exception they're exactly the same as before. The exception, base 30, doesn't have tests for the first six primes, because it's missing 11, but it does have tests for four of the next five primes! (The next five after the first six, not after 11.)

Unfortunately, I still haven't addressed the issue I brought up earlier, about the number, nature, and order of tests. After three tests, remember, base 10 has the advantage; but after four tests, base 12 is better again, because it covers the first six primes plus 19 and 29, while base 10 only covers the first six primes plus 37. But, no, that's not right, either … the next test in base 10 isn't the simple 3-test, which covers 37, it's the combined test based on 1003, which covers 17 and 59.

The point I'm trying to make is that the issue is complex. The correct sequence of tests in any given base depends not only on which tests happen to be available, but also on at least two variables: the size of the numbers you want to factor, and the number of products you're willing to learn. The 3-test, for example, is vastly more effective if you learn all the three-digit products; but there are almost twice as many three-digit products in base 12 as in base 10. So, I don't see any way to proceed from here except to actually go into each base and work out a complete system for factoring. Then, to compare bases, you could characterize them by plotting the probability of factoring as a function of the amount of effort required.

Anyway, it's pretty clear that base 10 is, if not the absolute best base, at least a surprisingly good one, and that base 12 and base 30 are also very good.

What other conclusions can we draw from the table?

• Hexadecimal and octal both look pretty poor; on the other hand, it seems to me that they both should be thought of as representations of binary. Of course, binary looks pretty poor, too, but it's sufficiently unusual that it ought to be considered separately. For example, tests with up to six digits could easily be considered simple, and those cover the first seven primes!
• Base 60 also looks pretty poor, and in this case I think that's an accurate conclusion. It may be convenient for everyday numbers, but it's just about useless for divisibility testing. Too bad 59 and 61 are both prime!

Finally, I wanted to say a few words about different ways of computing the table. While I was working on this essay, I thought of two such, by row and by column.

To compute a row, you basically just walk through the list of tests and factor the associated numbers. In base 34, for example, the number 10 (34) is 2×17, so those primes get marked with a “D”; then the number 1# (33) is 3×11, so those primes get marked with a “S”; and so on.

There are a few shortcuts, though, because some of the numbers can be partially factored in advance, even before the base is specified. The number 100# for the 3-test, for example, can always be written as 1# × 111; and then the first factor can be ignored, because it's just the number for the S-test. To put it another way, you can think of the numbers as being polynomials in the unspecified base b, then for example the factorization above can be expressed as

b³ − 1 = (b − 1)(b² + b + 1).

In the end, you only need to factor six numbers: b, b ± 1, c = b²+1, and c ± b.

If you're computing several rows in order, you'll notice a couple of regularities arising from how the numbers map from base b to base b+1. The numbers 10 and 11 map to 1# and 10, which causes the vertical “ADS” pattern in the table; and the number 111 maps to 1#1, which causes the vertical “33” pattern. The latter also manifests itself in the way that the larger primes often appear on two successive rows.

To compute a column, you have to do something completely different. Suppose that in some base b, some prime number p is covered by the 3-test. What does that mean? Well, it means that p is a factor of the number 100#; in other words, p goes evenly into b³ − 1. So, in still other words, it means the following, …

b³ ≡ 1 mod p

… and that equation, interpreted as a statement about the group of integers under multiplication mod p, means that b is an element of order 1 or 3. The other tests behave similarly, so if we want to know all about simple divisibility tests for p, we need to understand the group of integers mod p. Fortunately, that's not too hard. I'll explain by example, using p = 13.

First we need to guess a generator, a.k.a. a primitive root, and write out the group as powers of that generator. In this case, that's easy … I guess “2”, and it works. Then, by considering the size of the group, we can figure out which elements have the orders that we're interested in. Basically, the elements at positions 1/3 and 2/3 have order 3, and so on; but depending on the size of the group, there may not be any such elements.

element	1	2	4	8	3	6	12	11	9	5	10	7
order	1		6	4	3		2		3	4	6

After that, we just translate the orders into test names using the table below, …

order	n/a	1	2	3	4	6
test	D	S	A	3	2	3

… shuffle the elements into numerical order, and we're done.

element	0	1	2	3	4	5	6	7	8	9	10	11	12
test	D	S	-	3	3	2	-	-	2	3	3	-	A

The pattern repeats with length p, of course.

From here, we could go in all kinds of interesting directions, but I'll restrain myself and just point out three things.

• Because the group of integers mod 7 has size 6, the order of any element is a divisor of 6; therefore there's a simple divisibility test for 7 in any base.
• Similarly, there are hardly any simple tests for 11, because the group of integers mod 11 has size 10.
• The order of b mod p doesn't just tell us about divisibility tests, it's also the repeat length for the fraction 1/p in base b! So, there's a simple test for p if and only if the fraction is short.

For more about the integers mod p, see A Theorem on Finite Abelian Groups.