How Many Exceptions?

So … have I really explained the exceptions? Well, let's stop and see what we know. We know how to check whether a prime p is an exception, and how to calculate the number of anomalous steps; we also know that the exceptions are more or less random, and that they occur with probability 1/p. So, there's not much else we can say about why the specific values 3, 487, and 56598313 occur, that's just the way the cookie crumbles; but there is a little bit more we can say about why the exceptions are so unbelievably rare.

The key is to look at the expected number of exceptions. A prime p contributes one exception with probability 1/p, so the expected number for that prime is 1/p, and the total expected number up to some arbitrary limit n is sum(1/p), where the sum ranges over primes up to n. That sum doesn't have a nice closed form, but, as I just learned, it does converge to ln ln n … plus a constant c, approximately 0.261497, that's known as Mertens' constant. It's hard to grasp just how slowly the function ln ln n grows, so here it is in a table, along with some related quantities. (The value sum(1) is the number of primes up to n, and the function n/(ln n) is a simple approximation to it.)

n	sum(1)	n/(ln n)	sum(1/p)	ln ln n + c	sum(1/p2)
10	4	4.3	1.176	1.096	0.421519
100	25	21.7	1.803	1.789	0.450429
1000	168	144.8	2.198	2.194	0.452120
10000	1229	1085.7	2.483	2.482	0.452238
100000	9592	8685.9	2.705	2.705	0.452247
1000000	78498	72382.4	2.887	2.887	0.452247
10000000	664579	620420.7	3.041	3.041	0.452247
100000000	5761455	5428681.0	3.175	3.175	0.452247

Of course, when I said the sum converges to ln ln n + c, what I really meant was that sum(1/p) − ln ln n converges to c. The sum itself actually diverges, i.e., grows without bound; as a result, the total expected number of exceptions is infinite! That doesn't mean they're not rare, though … they are rare, and in fact now we can calculate exactly how rare they are. The density of exceptions is just the derivative of ln ln n, or 1/(n ln n) … as of course it must be since the density of primes is 1/ln n and the exception probability is 1/n. But, again, that's a bit hard to grasp, so let's try a different approach.

Suppose we want to find the next exception after 56598313. How far should we expect to have to search? In other words, for what value of n is the expected number of exceptions between 56598313 and n equal to 1? Well, if we take the difference of the total expected numbers at the endpoints, the constants cancel, and we have

ln ln n − ln ln 56598313 = 1,

and if we solve that, we find that n is 56598313^e, roughly 1.2×10²¹. Or, since we know there are no more exceptions below 2×10¹¹, we should really take that as the initial value, in which case we find that n is 5×10³⁰. (If we flip a coin, a run of tails doesn't make future heads more likely.)

So, now we know how many exceptions there are. Just for fun, let's also work out how many double exceptions there are, exceptions with two anomalous steps. The first part goes just as before … the probability of a double exception is 1/p², so the expected number is sum(1/p²). Like sum(1/n²), that sum converges; but unlike sum(1/n²), it doesn't converge to some simple combination of familiar numbers; the best we can do is say that it's approximately 0.452247. As far as I can tell, that number doesn't even have a name, it's just a value of the prime zeta function.

That page, by the way, contains an easy-to-miss link to another interesting thing, Artin's constant.

The significance of Artin's constant is more easily seen by describing it as the fraction of primes p for which 1/p has a maximal period repeating decimal, …

Now, however, we have to make a small correction. As I mentioned before, the case p = 2 is completely different. It's not even clear what should count as an exception … the non-exceptional rule, len(p^k) = p^k−1 len(p), doesn't hold in any base. So, just by definition, I'm going to say that p = 2 is not an exception. As a result, we should exclude it from the sum, and that leaves us with the value 0.202247. In any particular base, we should also exclude primes that are factors of the base, but I'm not going to worry about that here.

So, the expected number of double exceptions is 0.202247. From that, we can draw a couple of nice conclusions. For one thing, the number of double exceptions is finite with probability 1. For another, the probability of getting one or more double exceptions is close to but less than 0.202247 … around 20%, let's say.

For base 10 specifically, we can say even more. The three known exceptions are just single exceptions (I checked), so there are definitely no double exceptions below 2×10¹¹. And, as we can see from the table above, the sum has already pretty well converged by n = 10⁵. So, the probability that there are any double exceptions in base 10 is infinitesimal.