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

## How Many Exceptions?

prev

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 56598313e, roughly 1.2×1021. Or, since we know there are no more exceptions below 2×1011, we should really take that as the initial value, in which case we find that n is 5×1030. (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/p2, so the expected number is sum(1/p2). Like sum(1/n2), that sum converges; but unlike sum(1/n2), 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(pk) = pk-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×1011. And, as we can see from the table above, the sum has already pretty well converged by n = 105. So, the probability that there are any double exceptions in base 10 is infinitesimal.

next