Home> urticator.net Search About This Site > Domains Glue Stories Computers Driving Games Humor Law Math > Numbers Science Powers and Fractions Notes About Squares Decimal Expansions Repeat Length Again Number Maze Primes > Divisibility Intrinsic Nature of Primes Other Topics Other Topics (2) Reduction Rules Other Methods

In Other BasesIn this essay I'm going to present the results of an investigation I made on the subject of what divisibility and factoring are like in other bases. The investigation started from a question, isn't it strange that 1001 is the product of the second three primes?, and led to two surprising conclusions: the bases are not even close to equally good for factoring, and base 10 is quite good, perhaps the best.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.
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.
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.
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 base10 test for 5 will factor one in five numbers, or 20%; the base12 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 3test, 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 3test, for example, is vastly more effective if you learn all the threedigit products; but there are almost twice as many threedigit 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?
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 3test, 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 Stest. 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^{3}  1 = (b  1)(b^{2} + b + 1). In the end, you only need to factor six numbers: b, b ± 1, c = b^{2}+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 3test. What does that mean? Well, it means that p is a factor of the number 100#; in other words, p goes evenly into b^{3}  1. So, in still other words, it means the following,
b^{3} ≡ 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.
After that, we just translate the orders into test names using the table below,
shuffle the elements into numerical order, and we're done.
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.
For more about the integers mod p, see A Theorem on Finite Abelian Groups.

See AlsoAlgorithm, The Duodecimal Four Digits History and Other Stuff Multiplication in Base 10 Other Bases Other Methods Repunits Usual Random Thoughts, The @ November (2004) 