Thanks for the clarification. Reading back through the article I see where that's mentioned, but I totally missed it the first time through.

Ah I had missed it too. Is there a bound on the gap between subsequent primes as well?

For any natural n, the n consecutive numbers (n+1)! + 2, (n+1)! + 3, ... (n+1)! + (n+1) are all composite -- the first one is divisible by 2, the second one by three and so on.

Thus there are arbitrarily long sequences of consecutive numbers that have no primes in them.

I seem to remember that there's always a prime between n and 2*n? (Still an arbitrarily large absolute gap, but a fixed relative gap.)

Can anyone deny or confirm?

Yes, that's called Bertrand's postulate, first proven in 1850 by Chebyshev. For any integer n > 3, there's at least one prime strictly between n and 2n-2.

http://en.wikipedia.org/wiki/Bertrand's_postulate

Yes, you are right. http://mathworld.wolfram.com/BertrandsPostulate.html

That's a really damned cool proof. Why is it formulated as n+1 instead of merely n?

Because n! + 1 can be prime, so from n! + 2 to n! + n you only get n - 1 numbers.

That's why you need to start the sequence at (n+1)! + 2.

Concrete examples:

3!+1 = 7 is prime

11!+1 = 39916801 is prime (according to http://www.wolframalpha.com/input/?i=is+11!%2B1+prime%3F)

27!+1 = 10888869450418352160768000001 is prime (according to http://www.wolframalpha.com/input/?i=is+27!%2B1+prime%3F)

You forgot a couple.

1!+1 = 2 is prime.

2!+1 = 3 is prime.

Based on a back of the envelope estimate, the number of values of n up to N for which n!+1 is prime should be O(log(log(N))) so it should happen infinitely often. But proving that is likely to be difficult.

Did you get that estimate by some other way than using prime number theorem and Stirling approximation for n! ?

That is exactly how I estimated it.

But when I think about it, it is the wrong way to estimate it. Because you've eliminated all of the most common causes of those numbers not being prime, so the density of primes in that set should be expected to be massively higher than normal.

If I thought about it, I could come up with a much better estimate. But it would take some thought.

Presumably there's no semantic difference, though? Saying that, for any counting number n, there are at least n-1 consecutive composites is semantically no different than saying there are n consecutive composites. It just makes for a cleaner proof, no?

That's a neat little proof.

Just the opposite. The frequency of primes is known to be logarithmic, and therefore asymptotically approaches zero. From this, there cannot be such a thing as the largest gap between primes, because that would put a lower bound on the frequency of primes.

Nope :) Consider the number 1000000! + 1 (one million factorial plus 1).

  1000000! + 2 is divisible by 2.  
  1000000! + 3 is divisible by 3.  
  ...  
  1000000! + 1000000 is divisible by 1000000.

Here we have a gap of 999999 numbers, none of which are prime.

Weird, I just read about this exact example yesterday in the "music of primes" by Markus De Sautoy. I'm not sure though if it was the German Siegel or the Norwegian guy (Sebel or something) who also end up to Princeton to figure it out, or maybe it was known already by Euler's time :-)

Neat proof indeed.

I first read it a few years back in Excursion's in Number Theory [0]. Super approachable (and short!), I read it in high school with only a little bit of calculus knowledge.

[0]: http://www.amazon.com/Excursions-Number-Theory-Dover-Mathema...

That is a neat proof :D