# Is every natural number the truncation of a prime?

E.g. $$30$$ can be "extended" to a prime, namely 30$$19$$, and $$575$$ can be extended to a prime, namely 575$$4853343$$. Is this true for every natural number?

To make things precise:

Let $$n\in\mathbb{N}$$. Does there always exist a prime $$p=\sum_{i=0}^k d_i\cdot 10^i$$, where $$k\in\mathbb{N}_0$$ and $$d_i\in\{0,\ldots, 9\}$$, $$d_k\neq 0$$, $$i=0,\ldots, k$$, such that $$n=\sum_{i=l}^k d_i\cdot 10^{i-l}$$ for some $$l\leq k$$?

I thought of this problem randomly and find it interesting. My guess is that it is known, studied, but perhaps unsolved. Or trivial in a non-trivial way.

• See oeis.org/A018800 (and kudos for thinking of the problem for yourself). Aug 28, 2020 at 16:51
• @BarryCipra: Amazing, thanks. Feel free to post as an answer, so I can accept. Aug 28, 2020 at 16:55
• @DamianReding, your example $3019$ suggests a variant that people might find interesting: can you append a prime number to $n$ (with no leading $0$'s) to produce a prime? (Note, for $n=30$, the smallest prime appendage would be $7$, not $19$.) Aug 28, 2020 at 17:03
• @BarryCipra: Interesting! About the original problem: if I understand the proof in your link correctly, it easily extends to show that in fact there are always infinitely many primes with that property. Aug 28, 2020 at 17:06

If your number is $$n$$ and if you add $$k$$ zeroes after it, you get $$a=n\cdot 10^k$$. We are going to look for a prime greater than $$a$$ and less than $$b=(n+1)\cdot 10^{k}$$.

There are real numbers $$p,q$$ such that:

$$a=p^3=n\cdot10^k$$

$$b=q^3=(n+1)\cdot 10^{k}$$

or:

$$p=\sqrt[3]{n} \cdot 10^{k/3}$$

$$q=\sqrt[3]{n+1} \cdot 10^{k/3}$$

$$q-p=(\sqrt[3]{n+1}-\sqrt[3]{n})\cdot10^{k/3}\tag{1}$$

The first factor in (1) can be very small but we can choose a big $$k$$ and make difference $$q-p$$ as big as we want (say 10 or $$10^{10^{10}}$$).

So we are always able too choose $$k$$ such that there are at least two cubes between $$a$$ and $$b$$. Choose two consecutive cubes, $$r^3$$ and $$(r+1)^3$$ between $$a$$ and $$b$$. Notice that by increasing $$k$$ we can also make $$r$$ as big as we want.

Ingham proved that for big enough $$r$$ there is always a prime between $$r^3$$ and $$(r+1)^3$$. That prime will be between $$a$$ and $$b$$ and therefore starts with digits contained in number $$n$$.

• That's a rather huge hammer you're wielding. The fact that $$\lim_{k \to \infty} \frac{p_{k+1}}{p_k} = 1$$ (weaker than the PNT) suffices. Just take $k_0$ large enough that $p_{k+1} < \frac{n+1}{n} p_k$ for $k \geqslant k_0$, and $r$ large enough that $10^r\cdot n > p_{k_0}$. Aug 28, 2020 at 18:20
• @DanielFischer Big hammer or small, it cracked the nut :)
– Saša
Aug 28, 2020 at 18:55

It's a big hammer, but at least for the purposes of thinking through what sorts of results should and shouldn't be true of the primes, it's worth noting that this follows straightforwardly from the prime number theorem (PNT). In fact the PNT implies this asymptotic strengthening of Bertrand's postulate:

Claim: For any $$\epsilon > 0$$, there exists some $$n_{\epsilon}$$ such that for all $$n \ge n_{\epsilon}$$, there always exists a prime between $$n$$ and $$(1 + \epsilon) n$$.

Proof. The PNT says that $$\pi(n) \sim \frac{n}{\log n}$$, which means that

$$\lim_{n \to \infty} \frac{\pi((1 + \epsilon) n}{\pi(n)} = \lim_{n \to \infty} \frac{(1 + \epsilon) n \log n}{n \log (1 + \epsilon) n} = (1 + \epsilon)$$

so for some $$n_{\epsilon}$$ (large enough so that the above sequence ends up within, say, $$\frac{\epsilon}{2}$$ of its limit) we must eventually have that $$\frac{\pi(1 + \epsilon)n)}{\pi(n)}$$ is strictly greater than $$1$$ for all $$n \ge n_{\epsilon}$$, as desired. $$\Box$$

(The argument is insensitive to the precise meaning of "between" - strictly speaking what it shows is that there's a prime larger than $$n$$ and less than or equal to $$(1 + \epsilon) n$$, but by tweaking epsilon you can improve "less than or equal to" to "less than.")

This gives your desired result as follows. If $$a$$ is any positive integer, we want to know that there eventually exists a prime strictly between $$a \cdot 10^d$$ and $$(a + 1) \cdot 10^d$$. But this follows from the above claim by taking $$\epsilon = \frac{a + 1}{a}$$.

Oldboy uses a stronger result which at least roughly says that there's eventually a prime between $$n$$ and something like $$n + 3n^{2/3}$$ (although I don't know if it's strictly equivalent to a statement like this) and conjecturally it ought to be possible to improve this to something like $$n + \sqrt{n}$$.

I'll also note that when I saw only the title of your question I thought it referred to truncation of digits on the left rather than on the right; in this case it's also true that every natural number is the truncation of a prime, but the proof instead uses Dirichlet's theorem on primes in arithmetic progressions.

• Well done, this should be the accepted solution.
– Saša
Sep 26, 2020 at 5:56