36
$\begingroup$

That is, is it the case that for every natural number $n$, there is a prime number of $n$ digits? Or, is there some $n$ such that no primes of $n$-digits exist?

I am wondering this because of this Project Euler problem: https://projecteuler.net/problem=37. I find it very surprising that there are only a finite number of truncatable primes (and even more surprising that there are only 11)! However, I was thinking that result would make total sense if there is an $n$ such that there are no $n$-digit primes, since any $k$-digit truncatable prime implies the existence of at least one $n$-digit prime for every $n\leq k$.

If not, does anyone have insight into an intuitive reason why there are finitely many trunctable primes (and such a small number at that)? Thanks!

$\endgroup$
  • $\begingroup$ Anyway, yes: for all $n$ there are a lot of primes having $n$ digits. $\endgroup$ – Crostul Sep 10 '16 at 22:34
  • 10
    $\begingroup$ Bertrand's postulate (an ill-chosen name) says there is always a prime strictly between $n$ and $2n$ for $n\gt 1$. $\endgroup$ – hardmath Sep 10 '16 at 23:03
  • 5
    $\begingroup$ Think about the reverse. If you have an $n$-digit prime, how many 'chances' do you have to extend it to an $(n+1)$-digit prime? The odds being able to do so quickly turn against you. $\endgroup$ – Hurkyl Sep 11 '16 at 0:18
  • $\begingroup$ Just a side-comment - ..and even more surprising that there are only 11 ...Maybe I am wrong regrading your meaning , but I believe that there are 15 ( and not 11 ) both-sides truncatable primes .. Wiki entry on truncatable prime. $\endgroup$ – Obmerk Kronen Sep 11 '16 at 3:05
  • 1
    $\begingroup$ Via the Wikipedia article I found M. El Bachraoui's 2006 ["Primes in the Interval [2n, 3n]"](m-hikari.com/ijcms-password/ijcms-password13-16-2006/…) which relies on elementary methods and three results from an undergraduate textbook. $\endgroup$ – Keith McClary Sep 12 '16 at 1:52
79
$\begingroup$

Yes, there is always such a prime. Bertrand's postulate states that for any $k>3$, there is a prime between $k$ and $2k-2$. This specifically means that there is a prime between $10^n$ and $10\cdot 10^n$.

To commemorate $50$ upvotes, here are some additional details: Bertrand's postulate has been proven, so what I've written here is not just conjecture. Also, the result can be strengthened in the following sense (by the prime number theorem): For any $\epsilon > 0$, there is a $K$ such that for any $k > K$, there is a prime between $k$ and $(1+\epsilon)k$. For instance, for $\epsilon = 1/5$, we have $K = 24$ and for $\epsilon = \frac{1}{16597}$ the value of $K$ is $2010759$ (numbers gotten from Wikipedia).

$\endgroup$
  • 8
    $\begingroup$ With the side note that Bertrand's postulate is a (proved) theorem. $\endgroup$ – egreg Sep 11 '16 at 22:29
  • 1
    $\begingroup$ Just another note: those interested in this sort of thing should look for papers by Pierre Dusart - he has proven many of the best approximations of this form. $\endgroup$ – Carl Schildkraut Sep 14 '16 at 3:09
24
$\begingroup$

While the answer using Bertrand's postulate is correct, it may be misleading. Since it only guarantees one prime between $N$ and $2N$, you might expect only three or four primes with a particular number of digits. This is very far from the truth.

The primes do become scarcer among larger numbers, but only very gradually. An important result dignified with the name of the ``Prime Number Theorem'' says (roughly) that the probability of a random number of around the size of $N$ being prime is approximately $1/\ln(N)$.

To take a concrete example, for $N = 10^{22}$, $1/\ln(N)$ is about $0.02$, so one would expect only about $2\%$ of $22$-digit numbers to be prime. In some sense, $2\%$ is small, but since there are $9\cdot 10^{21}$ numbers with $22$ digits, that means about $1.8\cdot 10^{20}$ of them are prime; not just three or four! (In fact, there are exactly $180,340,017,203,297,174,362$ primes with $22$ digits.)

In short, the number of $n$-digit numbers increases with $n$ much faster than the density of primes decreases, so the number of $n$-digit primes increases rapidly as $n$ increases.

$\endgroup$
  • 2
    $\begingroup$ The prime number theorem will give you a bound on the number of primes between $10^n$ and $10^{n+1}$. But is the bound tight enough to prove that the number of such primes is a strictly growing function of $n$? $\endgroup$ – kasperd Sep 11 '16 at 8:33
  • 1
    $\begingroup$ @kasperd There are some known (explicit) estimates on the error term in the prime number theorem, I can imagine they are strong enough to show this, albeit possibly only for large $n$. $\endgroup$ – Wojowu Sep 11 '16 at 8:50
  • 1
    $\begingroup$ The prime number theorem on its own would allow for very large gaps between primes, but not so large that there are no primes between $10^n$ and $10^{n+1}$ when n is large enough. On the other hand, it is a limit, so it says nothing about small primes. $\endgroup$ – gnasher729 Sep 11 '16 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.