The Usual Random Thoughts

Now 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_p^k 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_2^k 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 p−1, and a secondary peak at the half length (p−1)/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 (p−1)/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¹⁵ (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.

2		1093   3511
3		11   1006003
4		1093   3511
5		20771   40487   53471161   1645333507
6		66161   534851   3152573
7		5   491531
8		3   1093   3511
9		11   1006003
10		3   487   56598313
11		71
12		2693   123653
13		863   1747591
14		29   353
15		29131
16		1093   3511
17		3   46021   48947
18		5   7*   37   331   33923   1284043
19		3   7*   13   43   137   63061489
20		281   46457   9377747
21
22		13   673   1595813
23		13   2481757   13703077
24		5   25633
25		20771   40487   53471161   1645333507
26		3*   5   71
27		11   1006003
28		3*   19   23
29
30		7   160541
31		7   79   6451   2806861
32		5   1093   3511
33		233   47441
34		46145917691
35		3   1613   3571
36		66161   534851   3152573
60		29

I don't have the computing power to run a truly gigantic search, but the table is complete up to 10⁸, 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⁸ 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 k−1; and if the base is adjacent to a multiple of p^k, then p is (again) an exception of order k−1. 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² = 1002001, with two zeroes at the end. And, of course, for any particular prime we can work out the multiplication table mod p² 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² is 243000000−1, so that 13233⁴ 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^k−1−d 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.

b	d	k	=	1	2	3	4	5	6	7
17	3+			1	1	1	1	2	4	8
15	3−			1	2	2	2	2	4	8

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^k−2. (You can use the first fact to prove the second … any number that ends in 101 has order 2^k−2 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.

• 5 starts with full length 4, and is an exception with d = 1, so the length will stay the same for one step, then increase by a factor of 5 per step.
• 2 starts with full length 1, and is classified as d = 2⁻ … not an exception, because 2 is never normal. Anyway, the length will increase by a factor of 2 for one step, stay the same for two steps, then increase by a factor of 2 per step.

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.

k	1	2	3	4	5	6	7
step		1	5	5	5	5	5
len(5k)	4	4	20	100	500	2500	12500
step		2	1	1	2	2	2
len(2k)	1	2	2	2	4	8	16
step		1	5	5	5	10	10
len(10k)	4	4	20	100	500	5000	50000