Monday, 11 October 2010

Prime number generalisation

The annoying (or fascinating) thing about prime numbers is that there is no pattern in their occurrence within the counting numbers.

In my last post I set this problem:

Here is a generalisation: "In every third decade starting with 10–19 there are at least three prime numbers."
[Every third decade would be: 10–19, 40–49, 70–79, 101–109, and so on.]
Is this a valid generalisation? Or can you find a counterexample?

First, let's say, without doing any investigation, that I would be very surprised if this proved to be valid, because patterns in the occurrence of prime numbers are elusive. I'm fairly confident that we should find plenty of counterexamples.

You could do this just by checking each decade until you find one that doesn't work. I'll leave you to do that, if you wish. You may have to check quite a lot of numbers! Note that you need to check only the four numbers in each decade that end in 1, 3, 7 and 9. Clearly, the even numbers and those ending in 0 and 5 are not prime. So, for example, in the decade 220–229 you have to check only 221, 223, 227 and 229.

Here's an approach that is more analytical.

The four crucial numbers in each decade we are considering are a multiple of 30 plus 11, or 13, or 17, or 19. For example, in the decade 220–229, the four numbers we need to check are 210 + 11, 210 + 13, 210 + 17 and 210 + 19, where 210 is a multiple of 30.

So, if we choose a multiple of 30 that is also a multiple of, say, 11 and 13, then the first two of the four crucial numbers will definitely not be prime Because they will be multiples of 11 and 13, respectively.

So, the decade I will manufacture as my counterexample is the one that begins with 11 x 13 x 30 + 10 = 4290 + 10. That is: the decade 4300–4309.

The argument is that 4301 = 4290 + 11, which must be a multiple of 11 because 4290 is a multiple of 11. (In fact 4301 = 391 x 11). And 4303 = 4290 + 13, which must be a multiple of 13 because 4290 is a multiple of 13. (In fact 4303 = 331 x 13).

So, there's my counterexample: the decade 4300–4309 does not contain three or more primes, because 4300, 4301, 4302, 4303, 4304, 4305, 4306, 4308 are all definitely not prime.

I do not need to check 4307 or 4309 to make my case. But, as it happens, neither of these is prime: 4307 = 59 x 73 and 4309 = 31 x 139.
So, by chance, I have discovered a decade without any prime numbers!