Primes Aplenty

Today, whilst at work, a colleague asked me what the largest prime number I know of is. I responded half-seriously with “seventeen” and then, like all of the best conversations had between humans, we steered into a good bout of prime number-related banter.

One of the questions that came up was this:

“Is there a prime number for every given number of digits?”

That is, we know that 3 is a prime with one digit, 17 is a prime with two digits, 181 is a prime with three digits, but can we always do this?  If we are given any whole number does there exist at least one prime number with exactly that many digits?

The answer is a sexy yes and – because I’m a good-natured chap with little to do on a Monday night except think about primes – I will quickly prove this for you. We will need the following theorem, which is probably a useful thing to know never.

Bertrand’s Postulate: For every x > 1, there is a prime number between x and 2x.

In simple terms, choose any number x greater than 1 and then double your number to get 2x. Bertrand’s postulate guarantees that there is a prime number between these two numbers x and 2x.

This makes our “prime of any digit” problem a cinch, as we want to be able to prove that there is a prime between 1 and 10, 10 and 100, 100 and 1000, 1000 and 10 000, and so on. In general, we want to prove that there is a prime between 10^m and 10^{m+1} for all m \geq 0.

Not too bad, huh? We just let x = 10^m and then Bertrand’s postulate tells us that there is a prime between 10^m and 2 \cdot 10^m. Clearly, 2 \cdot 10^m is less than 10 \cdot 10^m = 10^{m+1} and so we have proven the result.

This got me thinking more about prime numbers, which is something that I used to do quite a lot but gave up because I wanted to pay my rent and eat regularly. So here’s an additional fun fact for you:

There is a prime number for every given number of digits no matter what base you choose.

What does this mean? Good question. We proved above that there is a prime number for any given number of digits when we use the decimal (base 10) system. But what if we choose to write our numbers in binary (using 0’s and 1’s) or ternary (using 0’s, 1’s and 2’s)? Well, it turns out that we can still find primes of any number of digits, and actually the proof is pretty much the same as before (I’ll pull the classic trick of leaving this for the reader).

For example, here are our counting numbers written in binary, where I’ve put the prime numbers in red.

1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, …

This is really neat! The number of digits we need grows quite quickly in binary and yet we still manage to get a prime number for any given number of digits. Good times!

So are there other interesting facts to do with prime numbers and digits? Yes. Yes there are. I’ll give you two of them here because I’m a decent person.

Bonus Fact 1: For any string of digits, be it your phone number, credit card number or whatever, there are infinitely many prime numbers that contain that string of digits.

For example, let’s choose the number for Domino’s Pizza: 131 888. Then there are infinitely many prime numbers that contain this string in order within its digits. I’ll give you just one: 113188853. You can go looking for more if you like. I actually wrote a paper on this phenomenon (you can find it here) if you need to temper the salivation.

Bonus Fact 2: Pick a prime number. Its last digit hints at what the last digit of the next prime number will be.

Incredible. This is a brand new discovery as well. But here’s just one example of the phenomenon so that we’re on the same page here: a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9.

Earlier this year, the above discovery came as a shock surprise to the experts in the field. The usual school of thought was that the last digits of the prime numbers were distributed fairly randomly amongst 1, 3, 7 and 9, and that the last digit of a prime had nothing to do with what the last digit of the next prime is. But now we know differently. And it’s pretty crazy that nobody picked up on this earlier. Shame on you all.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s