Need a 12-digit prime?

Posted on by John

You may have seen the joke “Enter any 12-digit prime number to continue.” I’ve seen it floating around as the punchline in several contexts.

So what do you do if you need a 12-digit prime? Here’s how to find the smallest one using Python.

    >>> from sympy import nextprime
    >>> nextprime(10**11)
    100000000003L

The function nextprime gives the smallest prime larger than its argument. (Note that the smallest 12-digit number is 1011, not 1012. Great opportunity for an off-by-one mistake.)

Optionally you can provide an addition argument to nextprime to get primes further down the list. For example, this gives the second prime larger than 1011.

    >>> nextprime(10**11, 2)
    100000000019L

What if you wanted the largest 12-digit prime rather than the smallest?

    >>> from sympy import prevprime
    >>> prevprime(10**12)
    999999999989L

Finally, suppose you want to know how many 12-digit primes there are. SymPy has a function primepi that returns the number of primes less than its argument. Unfortunately, it fails for large arguments. It works for arguments as big as 2**27 but throws a memory error for 2**28.

The number of primes less than n is approximately n / log n, so there are about 32 billion primes between 1011 and 1012. According to Wolfram Alpha, the exact number of 12-digit primes is 33,489,857,205. So if you try 12-digit numbers at random, your chances are about 1 in 30 of getting a prime. If you’re clever enough to just pick odd numbers, your chances go up to 1 in 15.

5 thoughts on “Need a 12-digit prime?”

  1. But you would never guess a number ending in five, so we should be up to about 1/11. And numbers that are multiples of three are easy to eliminate so odds are even a little better for even a reasonable wag.

    Great post. SOMEDAY I will learn python.

  2. The ten zeros in 100000000003 raises another challenge. How about a prime with a particular number of zeros in it? I wonder how often the smallest prime of n digits is also the smallest prime with (n-2) zeros.

  3. John

    Eugene: The probability of a number around N being prime is roughly 1/log(N). So for N on the order of 10^12, there’s a 3 or 4 percent change of a number near N being prime. So it’s fairly likely there will be a prime between N and N+9, quite likely there will be a prime between N and N+99.

    If you want few zeros, look for numbers slightly less than N. That reverses the logic above. It’s moderately likely you’ll find a prime between N and N-9 and more likely you’ll find one between N and N-99.

  4. g

    Eugene: if there’s a prime of the form 100…00d then the smallest such will certainly be the smallest prime with its number of zeros. If not, it’s vanishingly unlikely that there’s no other prime with that many digits before the first with that many zeros.

    So your question is more or less equivalent to asking how often there’s a prime 100…00d. The only candidates are d=1,3,7,9, and choosing one of these guarantees you’re good mod 2,3,5, so the density of such primes is about 15/4log(n) and very crudely the chance that one of those four is prime is about 15/log(n), or 15/log(10).1/#digits. (Actually #digits-1, but we’re interested in large #digits.)

    Except that for more than 3 digits we can rule out d=1 too. (10^n+1 is a multiple of 11 when n is odd, a multiple of 101 when n is 2 mod 4, a multiple of 10001 when n is 4 mod 8, etc.; so it can only be prime for n a power of 2; and, though no one’s proved it, probably there are no other primes of this form, just as probably there are no Fermat primes beyond the ones Fermat found.) So our numbers need reducing by a factor of 3/4. And then increasing by a factor of 11/10 because now we’re guaranteed OK mod 11 too.

    So, barring weirdness of the sort no one expects but I bet no one knows how to disprove (density of primes being systematically different near to powers of 10), this happens with probability about 5.4/d for d-digit numbers, hence about 5.4 log(d) times among numbers of at most d digits.

    (A bit of numerical experimentation produces smaller numbers than these, so maybe my constant factor is screwed up for some reason, but the general form is right.)

Comments are closed.