> urticator.net

  About This Site
> Domains

> Numbers

  Powers and Fractions
  Notes About Squares
  Decimal Expansions
> Repeat Length Again
  Number Maze
  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


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.

21093   3511
311   1006003
41093   3511
520771   40487   53471161   1645333507
666161   534851   3152573
75   491531
83   1093   3511
911   1006003
103   487   56598313
122693   123653
13863   1747591
1429   353
161093   3511
173   46021   48947
185   7*   37   331   33923   1284043
193   7*   13   43   137   63061489
20281   46457   9377747
2213   673   1595813
2313   2481757   13703077
245   25633
2520771   40487   53471161   1645333507
263*   5   71
2711   1006003
283*   19   23
307   160541
317   79   6451   2806861
325   1093   3511
33233   47441
353   1613   3571
3666161   534851   3152573

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.


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.



  See Also

  Multiplication in Base 10
  Two Kinds of Odd

@ April (2006)