Home

> urticator.net
Search

> Domains
Glue
Stories

Computers
Driving
Games
Humor
Law
Math
> Numbers
Science

Powers and Fractions
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 Thoughts

## The Usual Random Thoughts

prev

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 Upk is cyclic, given that Up is. I think that makes a nice footnote to The Structure of Un. (Caveat: the argument does not apply for p = 2, and in fact the groups U2k 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×1015 (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 108, 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 108 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 bk, 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 pk, 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 282 = 1002001, with two zeroes at the end. And, of course, for any particular prime we can work out the multiplication table mod p2 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 pk, so p is an exception in base qwhatever; 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 132332 is 243000000-1, so that 132334 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(2k) 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(pk) = pk-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 2k-2. (You can use the first fact to prove the second … any number that ends in 101 has order 2k-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/10k 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