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) Multiplication in Base 7 The Exceptions Explained How Many Exceptions?

The Usual Random ThoughtsNow we come to the usual random thoughts exploding in different directions at the end … only this time there are so many of them that I had to split them off into their own subessay. I'm not even going to try to tie them together, I'm just going to jump from one to the next without warning. The argument that we used in The Exceptions Explained to show that the orders increase by factors of p can also be used to prove that U_{pk} is cyclic, given that U_{p} is. I think that makes a nice footnote to The Structure of U_{n}. (Caveat: the argument does not apply for p = 2, and in fact the groups U_{2k} are not cyclic for k >= 3.) Regarding the probability distributions for len(p), there are some general rules that apply. For p = 2, the length is always 1. For any other prime, there are always two major peaks: a primary peak at the full length p1, and a secondary peak at the half length (p1)/2. The secondary peak is the same size as the primary if p ≡ 3 mod 4, otherwise half the size. No other peak is more than half the size of the primary, so if you have to guess a length, the full length is as good a guess as any. Actually, that's not quite true … you can use quadratic residues to rule out either the primary or the secondary peak. I learned that from an excellent article by Helmut Richter—who ran the exception search in base 10!—and I can't explain the result any better than he does.
In other words, we have to find K such that the period length is (p1)/K. In which cases K is even can be determined by quadratic residues: K is even if and only if the base b of the number system is a quadratic residue modulo p. For base 10, this is the case if and only if the distance of p to the nearest multiple of 40 is one of 1, 3, 9, or 13. So, in the listed cases, you should guess the secondary peak instead. The exceptions in base 2 are much more famous than the exceptions in base 10. They're called Wieferich primes (see also A001220), and only two are known, 1093 and 3511, even though the search has been carried quite a bit further than in base 10.
… a limit since increased to 1.25×10^{15} (McIntosh 2004) No, that's not me, in case you were wondering. Strangely, I'd heard of Wieferich primes only once before, when I was reading about Catalan's conjecture (that I mentioned in Sharps and Flats) … apparently they figure into the proof somehow or other. I couldn't find any lists of exceptions in other bases, so I ran the numbers myself, and here are the results. An entry marked with an asterisk is a double exception.
I don't have the computing power to run a truly gigantic search, but the table is complete up to 10^{8}, and also includes two larger numbers that I saw elsewhere, so that it represents everything I know about the listed bases. The results agree with the sequence A039951 if we take into account the fact that I've excluded 2. Also, according to the other table, the expected number of exceptions below 10^{8} is 3.175, or rather 2.675 after we exclude 2, and the results seem to agree fairly well with that, too. The rows for base 21 and base 29 are blank, and the row for base 34 has only the one larger number … sounds like a reason to use one of them as a base! (Base 21 and base 34 are also good for divisibility testing.) There are a few patterns we can observe: if the base has the form b^{k}, then it has at least the same exceptions as base b; if also k is divisible by a prime p, then p is an exception of order k1; and if the base is adjacent to a multiple of p^{k}, then p is (again) an exception of order k1. The third pattern has a particularly simple explanation. For example, 3 is an exception in base 28 because 28 in base 3 is 1000+1, so 28^{2} = 1002001, with two zeroes at the end. And, of course, for any particular prime we can work out the multiplication table mod p^{2} and determine the complete pattern. For example, p = 7 is an exception if the base is congruent to 1, 18, 19, 30, 31, or 48 mod 49. Hey, actually, those patterns are all we need to see the connection to Catalan's conjecture! Suppose the primes p and q have adjacent powers. The power of p is (trivially) a multiple of p^{k}, so p is an exception in base q^{whatever}; but then p is also likely to be an exception in base q. By symmetry, however, q is likely to be an exception in base p, so that the primes form a double Wieferich prime pair! What about exceptions with multiple anomalous steps, i.e., with d >= 2? We can already see some with d = 2 in the table: 3 in bases 26 and 28, as a result of the third pattern, and 7 in bases 18 and 19, for no particular reason. That article by Richter mentions a few good ones with d > 2: 13 in base 239 and 5 in base 443, with d = 3, and 5 in base 1068, with d = 5! Let's look at that last one in more detail. 1068 written in base 5 is 13233, nothing unusual there, but then 13233^{2} is 2430000001, so that 13233^{4} ends in 000001, as expected. Or, looking at it the other way 'round, in base 5 the square root of 73 (243) is 13.23300001213. We can actually see an echo of that in base 10, where it's 8.54400374532. Now, at long last, I'm going to tell you what I know about p = 2. Let's start with the practical side of things. If we're working in base b and want to understand how the sequence len(2^{k}) behaves, then just as for any other prime p we need to switch to base p and find the first power of b that ends in 1. However, b must be odd, or we'd have discarded 2 … and every odd number ends in 1 in base 2! So, we just need to write down the number b itself in base 2. If the number ends in 01, everything goes as before … d is equal to the number of trailing zeroes, and the lengths obey the improved rule
len(p^{k}) = p^{k1d} len(p), albeit never with d = 0. If the number ends in 11, though, things are different … we need to take the twos complement before we count the zeroes, and if the rule tells us the length is 1, we should use 2 instead. I'm going to use the notation d^{+} and d^{} for the two cases, to distinguish them from each other and to remind us that p = 2 is different. To bring all that down to earth, here's a small table of repeat lengths.
On the theoretical side, I'm not going to prove all that, but I will mention a few helpful facts I discovered. First, if you square a number that ends in 01 and has n trailing zeroes, you get a number that ends in 01 and has n+1 trailing zeroes. Second, such numbers—numbers that are congruent to 1 mod 4—form a cyclic subgroup of order 2^{k2}. (You can use the first fact to prove the second … any number that ends in 101 has order 2^{k2} and so is a generator.) Third, you can get to the rest of the group by negating. Finally, to tie everything up in a nice little package with a bow on top, let's go back to base 7, to the rules for computing len(n), and to that old favorite of mine, 2401, and see what we can say about the length of 1/10^{k} in base 7. In Powers of N, remember, I said that 1/100 has the same length as 1/10 because 2400 is divisible by 100 … that's true, but it's hardly the whole story. The way I see it now, we should factor 10 as 5 × 2 and look at the components.
When we take the least common multiple of the two, though, the factor of 4 from the 5 side covers up the 2 side for quite a while.

See AlsoDuodecimal Multiplication in Base 10 Repunits Two Kinds of Odd @ April (2006) 