67
$\begingroup$

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?

$\endgroup$
5
  • 4
    $\begingroup$ It's unlikely to contain π as a substring, because π contains a decimal point and this string doesn't. Do you mean "every integer"? $\endgroup$
    – gnasher729
    Aug 30, 2014 at 23:26
  • 2
    $\begingroup$ No minus signs, @gnasher729. So has to refer to non-negative integers. :) $\endgroup$ Aug 30, 2014 at 23:27
  • 4
    $\begingroup$ See Copeland-Erdos constant. $\endgroup$
    – Lucian
    Aug 30, 2014 at 23:30
  • 1
    $\begingroup$ @Buddha, you didn't mention natural numbers, so change your question. And extending it to reals would be stupid because your string doesn't contain a decimal point or a minus character, so it doesn't contain the numbers 1.5 and -2, for example. $\endgroup$
    – gnasher729
    Aug 30, 2014 at 23:34
  • 3
    $\begingroup$ Possible duplicate of Proof that there are infinitely many prime numbers starting with a given digit string $\endgroup$
    – Watson
    Nov 28, 2018 at 12:57

4 Answers 4

82
$\begingroup$

It follows from Dirichlet's Theorem.

If $d$ is the number we want to find, define $s=10d+1$. By definition, $\gcd(s,10)=1$ and $s$ contains the digits of $d$.

Dirichlet's Theorem's implies there's a prime of the form $p:=s+k \times 10^n$ where $10^n$ is chosen so that it has as many zeroes as digits of $s$. The digits of $d$ appear in the digits of $p$, and thus in the given string of primes.

$\endgroup$
2
  • 1
    $\begingroup$ Very nice! This is actually exercise 4.16.b in Apostol's Introduction to Analytic Number Theory. $\endgroup$
    – Greg Hurst
    Aug 31, 2014 at 5:28
  • $\begingroup$ You should add that $k\in\mathbb N_{\ge 0}$. $\endgroup$
    – user26486
    Aug 31, 2014 at 13:26
34
$\begingroup$

If you mean "every non-negative integer", then the answer is yes.

First, it contains the integer 0 as a substring because 101 is a prime.

Next, for every integer i > 0, there is a prime that starts with the integer i: Take the known results about gaps between prime numbers, for example that there is always a prime between $n^3$ and$(n+1)^3$ for large n. There is always a large n such that both $n^3$ and$(n+1)^3$ start with the digits of i, therefore the prime between $n^3$ and$(n+1)^3$ also starts with the digits of i.

(This is true because one of i, 10i and 100i is not the cube of an integer).

$\endgroup$
2
  • 1
    $\begingroup$ I love that you have two solutions here: you show that every $k$ is a prefix of a prime written in the decimal system, the other answer shows that every $k$ is a suffix of it :) $\endgroup$
    – yo'
    Aug 31, 2014 at 19:56
  • 2
    $\begingroup$ @tohecz Yes, it actually means there's no need to string the primes together, simply $2,3,5, \dots$ will contain all natural numbers somewhere. $\endgroup$
    – Mark Hurd
    Sep 2, 2014 at 1:54
4
$\begingroup$

Let $n$ be a natural number, and let $\mathcal N(n)$ be the set of natural numbers not containing $n$ as a substring when written in base 10. It is well-known that $\sum_{k\in \mathcal N(n)}\frac{1}{k}$ converges.

Let $\mathcal P$ be the set of prime numbers. It is also well-known that $\sum_{p \in\mathcal P}\frac{1}{p}$ diverges.

Therefore it cannot be the case that $ \mathcal P\subseteq\mathcal N(n)$, and $n$ is therefore a substring of some prime (of infinitely many primes, in fact).

$\endgroup$
1
$\begingroup$

It follows from the fact that the Copeland-Erdös constant is a normal number.

For any natural number $N$ with $k$ digits, $N$ appears in the Copeland-Erdos constant with a natural density of $10^{-k}$.

$\endgroup$

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.