# Are there arbitrarily large gaps between consecutive primes? [duplicate]

I made a program to find out the number of primes within a certain range, for example between $1$ and $10000$ I found $1229$ primes, I then increased my range to $20000$ and then I found $2262$ primes, after doing it for $1$ to $30000$, I found $3245$ primes.

Now a curious thing to notice is that each time, The probability of finding a prime in between $2$ multiples of $10000$ is decreasing, i.e it was $$\frac{2262-1229}{10000}=0.1033$$ between $10000$ and $20000$, and $$\frac{3245-2262}{10000}=0.0983$$ between $20000$ and $30000$,

So from this can we infer that there will exist two numbers separated by a gap of $10000$ such that no number in between them is prime? If so how to determine the first two numbers with which this happens? Also I took $10000$ just as a reference here, what about if the gap between them in general is $x$, can we do something for this in generality?

Thanks!

• If you let $p$ be the largest prime below $10\,000$, then the interval $[p\# - 10\,002, p\# - 2]$ certainly contains no primes (where $p\#$ is the primorial). It's probably not the first time, though – Arthur Feb 28 '16 at 10:26
• In the same spirit as Arthur's suggestion, there are no primes among the $k$ consecutive numbers $(k + 1)! + 2, \ldots, (k + 1)! + (k + 1)$. – Travis Willse Feb 28 '16 at 10:31
• @Arthur largest prime below $10000$ is $9973$, and by p# do you mean $$2.3.5....9973$$? . – Nikunj Feb 28 '16 at 10:42
• @Travis This looks interesting, could you please provide a proof? – Nikunj Feb 28 '16 at 10:43
• @Nikunj Yes, that is what I mean by $p\#$. – Arthur Feb 28 '16 at 10:46

The Prime Number Theorem states that the number of primes $\pi(x)$ up to a given $x$ is $$\pi(x) \sim \frac{x}{\log(x)}$$ which means that the probability of finding a prime is decreasing if you make your "population" $x$ larger. So yes, there exist a gap of $n$ numbers whereof none are prime.

The way to find the first gap for some $n$ has to be done through the use of software, since the exact distribution of prime numbers is only approximated by $\frac{x}{\log(x)}$.

EDIT: That the PNT implies that there's always a gap of size $n$ can be seen by considering what would happen if this was not the case; if there was a maximum gap of $n$ that was reached after some $x$, the probability of finding a prime between $x$ and some larger number $m$ would no longer decrease as $m \to \infty$, which contradicts the PNT.

• @Nikunj Yes, this is indeed only good for larger $x$, but since this approximation holds for any $x$, $10,000-20,000$ are very small numbers. But yeah, it's the best that we have as of yet :) – Bobson Dugnutt Feb 28 '16 at 12:12
• @BenMillwood Yeah, that is an unfortunate choice of words, I'll edit it! Thanks! – Bobson Dugnutt Feb 28 '16 at 15:09
• Could you elaborate on this just a little bit? You're right that the PNT implies that at some point you have to have n integers without a prime, or else π(x) could never be sub-linear, but I feel like this is a few too many steps away from a proof. – hobbs Feb 29 '16 at 6:31
• @hobbs: If you never had $n$ integers without a prime, then the number of primes up to a given $x$ could never be less than $\lfloor{x/n}\rfloor$. This contradicts the PNT. – mjqxxxx Mar 1 '16 at 3:54
• @mjqxxxx I'm not asking for me, I'm asking for it to be made more explicit in the answer for others' benefit :) – hobbs Mar 1 '16 at 4:12

Can we infer that there exist two numbers separated by a gap of $10000$, such that no number in between them is prime?

We can infer this regardless of what you wrote.

For every gap $n\in\mathbb{N}$ that you can think of, I can give you a sequence of $n-1$ consecutive numbers, none of which is prime.

There you go: $n!+2,n!+3,\dots,n!+n$.

So there is no finite bound on the gap between two consecutive primes.

• @Nikunj: Not necessarily. Also, the gap is not guaranteed to be exactly $n$ (or $10000$ in your example). That is why I have emphasized the specific part of your question to which I am referring in my answer. – barak manos Feb 28 '16 at 11:05
• @Nikunj because $n! + 1$ and/or $n! + n + 1$ may be composite as well, in which case one gets a sequence of $> n - 1$ consecutive composite numbers. This is the case, e.g., for $n = 3$. – Travis Willse Feb 28 '16 at 11:42
• @Nikunj To give a specific example in which both $n! + 1$ and $n! + n + 1$ are composite, observe that $5! + 1 = 121 = 11^2$ and $5! + 6 = 126 = 2 \cdot 3^2 \cdot 7$. In fact, the numbers $$114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126$$ are all composite. – N. F. Taussig Feb 28 '16 at 11:56
• @barakmanos I would say, more precisely, that is a lower bound of $n$. – PyRulez Feb 28 '16 at 18:23
• @goblin Take any $n!+i$ with $2\leq i \leq n$. You can factor out an $i$ from the factorial since $i \leq n$, so you get $i(k + 1)$, for $i > 1$ and $k > 1$, where $k = n!/i$. – TokenToucan Feb 29 '16 at 2:33

We cannot infer from the two observations in the question that there are gaps of arbitrary sizes between primes. As Lovsovs mentions in his answer, this does follow from the Prime Number Theorem (one needs suitable error bounds on the approximation $\pi(x) \sim \frac{x}{\log x}$, but even crude ones will do here).

As asked in the comments, it's easy to construct for any positive integer $k$ a sequence of $k$ consecutive composite numbers. For any positive integer $a \leq k + 1$, $a$ divides $(k + 1)!$, and so it divides $(k + 1)! + a$, but this implies that each of the $k$ numbers $(k + 1)! + 2, \ldots, (k + 1)! + (k + 1)$ is composite. (This is generally not the first sequence for which this is true: For example, for $k = 3$, the resulting sequence is $26, 27, 28$, but the first sequence of three consecutive composite positive integers is $8, 9, 10$.)

• (+1) Thanks a ton for the proof, Is there no other way besides the use of software to look for the first such sequence? – Nikunj Feb 28 '16 at 11:02
• @Nikunj No, because (as stated in my answer) we do not know the exact distribution of primes. – Bobson Dugnutt Feb 28 '16 at 11:33
• In general the problem is difficult, so yes, for sufficiently large $k$ computer assistance is necessary. Note that the primorial $(k - 1)\#$ is much smaller than the factorial $(k + 1)!$ for even modest $k$, so Arthur's solution gives a much better upper bound for the position of the first such sequence, but in general it too is a pretty poor bound: Already for $k = 5$ it gives $204, \ldots, 208$, but the first sequence of five consecutive composite numbers is $24, \ldots, 28$. – Travis Willse Feb 28 '16 at 11:40
• @ travis : proving $\pi(x) = o(x)$ is much easier than the prime number theorem, for example it follows directly from $s \int_1^\infty \pi(x) x^{-s-1} dx \sim \ln \zeta(s) \sim -\ln(s-1)$ when $s \to 1^+$. – reuns Feb 28 '16 at 12:21

The problem of finding large gap between consecutive primes is an old and well studied one. There certainly is a large gap between what we know to be true, and what we suspect.

As for what people expect, Cramer's random provides a good source heuristics. Roughly spreaking, you can think of a number $n$ to be "prime with probability $\frac{1}{\log n}$", but sometimes you also have to take into consideration that the primes tend not to be divisible by $2, 3, 5,$, etc. Apparently, if you make a lot of optimistic assumptions, then you can reach the conclusion that the longest gap between primes in integers $\leq X$ is roughly $\log^2 X$. Hence, if you want your gap to have size $g$, then you should look at integers $\leq e^{\sqrt{g}}$ (which, for $g = 10000$ is pretty large). See this post of Terence Tao for details.

Much less has been proved. The best known bounds for the largest gap between primes is due to Kevin Ford, Ben Green, Sergei Konyagin, James Maynard, Terence Tao, and says that the largest gap below $X$ is at least $c \frac{\log X \log \log X \log \log \log \log X}{\log \log \log X}$, where $c$ is a constant.

• In the last para, I guess “largest gap between integers” should be “…between primes”. I believe there are fairly sharp upper and lower bounds known for gaps between consecutive integers :-P – Peter LeFanu Lumsdaine Feb 28 '16 at 15:54
• @PeterLeFanuLumsdaine: Thanks! I suppose the bound is no longer true for integers, but maybe I'll check with one of the authors ;) – Jakub Konieczny Feb 28 '16 at 16:56
• That "best known bound" is amazingly low if you consider that the average gap between primes is log X, so that average gap is improved by less than a factor c log log X. And c might be considerably smaller than 1. – gnasher729 Feb 29 '16 at 23:08
• @gnasher729: It is rather far from the prediction, yes. But it should be pointed out that we're much better in predicting things about the primes than in actually proving them. – Jakub Konieczny Mar 1 '16 at 3:10
• Are there any known bounds on $c$? – Brevan Ellefsen Dec 11 '16 at 17:56

Any sequence with density $0$, in most reasonable meanings of "density $0$", has arbitrarily large gaps.

This is true (for example, and in increasing order of generality) if density $0$ is interpreted as:

• the density on $[1,n]$ converges to $0$, or

• the lim inf of the density on $[1,n]$ is $0$, or

• the lim inf of the density on intervals of length $n$ is $0$

The asymptotic density of primes $\pi(n)/n \to 0$ is 0-density in the strong sense, which is more than enough to ensure large gaps.

The $n!$ examples of large gaps can be reduced from factorial to "primorial" size and the latter seems to be the best currently known deterministic construction.

This isn't going to be a fancy answer, (secondary school student) but I would believe it to be as a number rises the number of possible factors of the number also rise meaning there is a larger chance of it having more factors than itself and one. So a number has every number smaller than it as a possible factor, so smaller numbers have less possible factors and therefore less chance of more than 1 factor and itself.

There several factors determining the size of gaps. As per you example 10,000 has a square root of 100 which give you 25 prime number divisors for the 10,000 and the 20,000 square root is 141 and 34 divisors, and the 30,000 square root is 173 and 40 divisors. The number of divisors helps to determine the gaps. The number of factors needed is based on the square root of your max number. The square roots are decreasing percentage of the max number: example 100 / 10000 = 1.000%, 141 / 20000 = .70500% and 173 / 30000 = .57666%. The number of factors increased against the square root but decreases against the max number. Example: 106,749,747,000,000 the square root is 10,331,977 the square root % is .00000968% with 685,159 factors the max gap in my sample 712. The large gaps seam to have a cycle pattern to them.