Prime interruption

Suppose you have a number that you believe to be prime. You start reading your number aloud, and someone interrupts “Stop right there! No prime starts with the digits you’ve read so far.”

It turns out the person interrupting you shouldn’t be so sure. There are no restrictions on the digits a prime number can begin with. (Ending digits are another matter. No prime ends in 0, for example.) Said another way, given any sequence of digits, it’s possible to add more digits to the end and make a prime. [1]

For example, take today’s date in ISO format: 20181008. Obviously not a prime. Can we find digits to add to make it into a prime? Yes, we can add 03 on to the end because 2018100803 is prime.

What about my work phone number: 83242286846? Yes, just add a 9 on the end because 832422868469 is prime.

This works in any base you’d like. For example, the hexadecimal number CAFEBABE is not prime, but CAFEBABE1 is. Or if you interpret SQUEAMISH as a base 36 number, you can form a base 36 prime by sticking a T on the end. [2]

In each of these example, we haven’t had to add much on the end to form a prime. You can show that this is to be expected from the distribution of prime numbers.

Related posts

[1] Source: R. S. Bird. Integers with Given Initial Digits. The American Mathematical Monthly, Vol. 79, No. 4 (Apr., 1972), pp. 367-370

[2] CAFEBABE is a magic number used at the beginning of Java bytecode files. The word “squeamish” here is an homage to “The Magic Words are Squeamish Ossifrage,” an example cleartext used by the inventors of RSA encryption.

7 thoughts on “Prime interruption

  1. We can also ask how many such primes there are. If n is the number and b is the base, there are b^k numbers formed by adding k base-b digits after the digits of n. Based on the prime number theorem, the proportion of those that are prime should be roughly 1/log(nb^k) = 1/(log(n) + k log(b)).

    In fact, since 1/(log(n) + k log(b)) is a divergent series, turning my arbitrary string of digits into a prime is not just possible but almost certain, in the sense that I could read off a string of random digits and eventually read off a prime. (Although it is likely that I will die of old age before that happens, as the harmonic series diverges very slowly. This is also not a rigorous proof because the random digits do not result in independent random numbers, but it is certainly something that we expect to be true.)

  2. OK, let’s take a favorite irrational number, say pi or e or sqrt(2), and start reading the digits.

    How often should we expect a prime to arise? Are there any properties of the number that would affect this expectation?

  3. On the subject of primes, do you have any insight as to why a surprisingly large number of quadratic equations have a much higher prime density than expected (Hardy Littlewood Conjecture F, Ulam spiral, Sachs prime number spiral)? Is this just random happenstance that fades out in numbers beyond 10^100, or does it reflect some possible deeper structure of prime number distribution that isn’t well understood?

  4. I don’t understand what’s behind the Ulam spiral et al. My impression is that the phenomena you’re talking about is partially understood but not fully.

  5. Sigh. My thought was, once again, way too good to have been original.

    Plagiarizing it back into it’s original forum takes real talent!

Comments are closed.