When I’m doing my daily run, I frequently amuse myself by mentally determining the prime factorization of any three or four digit number I see. Doing so this morning got me thinking about prime numbers in general and made me wonder something.
I think most of us know Euclid’s proof that there are infinitely many prime numbers. It seems to me that that argument, and others like it, can be described as proving that number of integers between any given prime and the next larger one can never be infinite; it it were, the first integer would be the largest prime. Assuming I’m write about that (and I could easily be wrong), I wonder if there’s any way of calculating the maximum space (i.e., number of integers) between prime numbers.
Note that the above proof (which is very nice) doesn’t give you a sequence of exactly n composite numbers, bounded on each end by primes; it just gives you a sequence of at least n composite numbers for any n. Which is sufficient to show that no largest gap exists, of course.
It’s also known that the primes become rarer and rarer as you go to higher and higher integers; specifically, the probability that a given integer near N is prime is proportional to 1/ln(N) for sufficiently large N, which goes to zero as N goes to infinity. (I’m glossing over a bunch of formal definitions here, of course.) If there was a maximum gap between consecutive primes (call this number G), one would expect that this probability would instead approach 1/G as N went to infinity, rather than approaching zero.
I’m almost positive that there is some (really, really large number) after which primes start to become more common. I mostly remember that because it seems impossible.
Not directly related, but there was a recent paper I heard about, IIRC, there being an infinite number of paired primes no farther apart than 70,000,000 and can possibly be reduced significantly, maybe even being a path to proving the twin prime conjecture. Supposedly, since that paper was released they’ve already worked it down a lot. Not sure how much the OP is interested in this, but still cool stuff nonetheless.
Here’s a link to an article that covers the paper. I’m not sure how up to date it is.
ETA: Numberphile is awesome. I think that might even be where I heard about this paper.
I didn’t know that (the n > 100 part although it is plausible), but the following is true: For all epsilon > 0, there is an N such that n > N implies there is always a prime between n and n*(1+\epsilon). So the above claim is that when epsilon = 0.2, you can take N = 100. Finally, I cannot leave this thread without quoting the couplet that Nat Fine gave us when I took number theory 56 years ago and I have not been able to forget.
Chebychev proved it, you can too
There’s always a prime 'tween n and n times 2.
Incidentally, you can prove that trivially from Goldbach’s conjecture. Which isn’t much use since the n<p<2n thing is actually proven and Goldbach’s conjecture isn’t, but there you go.
Poetic license. Also, 0 is excluded since factorization is essentially about positive integers and there is a prime between 1 and 2 for some value of “between”.
The average distance between from a prime p to the next prime is unbounded by the argument already given above, but its “average” value is ~log p by the prime number theorem (where “average” requires more effort to define than I’m putting in at the moment). The primes are also “evenly distributed” (same caveat as above) modulo an arbitrary prime, so that the “average” (scare-quotes yet again) distance from a prime p to the next prime that’s equal to N mod q (for N != 0 mod q) is about ~(q-1)log p for a fixed prime q. There are extensive results on the distribution of primes, prime gaps, twin and similar primes, etc. It’s a huge field, but it’s not my field, so I’ll stop here.
