42
$\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$
7
  • $\begingroup$ Anyway, yes: for all $n$ there are a lot of primes having $n$ digits. $\endgroup$
    – Crostul
    Sep 10, 2016 at 22:34
  • 11
    $\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, 2016 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$
    – user14972
    Sep 11, 2016 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, 2016 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, 2016 at 1:52

2 Answers 2

Reset to default
88
$\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$
2
  • 9
    $\begingroup$ With the side note that Bertrand's postulate is a (proved) theorem. $\endgroup$
    – egreg
    Sep 11, 2016 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, 2016 at 3:09
32
$\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$
4
  • 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, 2016 at 8:33
  • 3
    $\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, 2016 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, 2016 at 18:49
  • $\begingroup$ The bounds from Wikipedia $\frac{x}{\log x + 2} < \pi(x) < \frac{x}{\log x - 4}$ for $x> 55$ can be used to show that there is always a prime with $n$ digits for $n\ge 3$. $\endgroup$
    – Dark Malthorp
    Oct 13, 2020 at 13:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .