Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To prove the following fact: given any sequence of digits in any base, eg 314159265358979323 base 10, there are infinitely many primes that start with these digits,eg when expressed in decimal they start with 314159265358979323. I think using a prime number theorem will be helpful . But I am still not getting a point of how to start the proof.

share|improve this question

migrated from stackoverflow.com Aug 30 '11 at 22:24

This question came from our site for professional and enthusiast programmers.

1  
The "Algorithms" in the title doesn't seem appropriate. –  Srivatsan Aug 30 '11 at 22:28
    
@Sri: Any suggestions for a better title? You could propose one by clicking edit, and users with sufficient rep can approve it if it's hunky-dory. –  J. M. Aug 30 '11 at 22:32
    
Note that "$n$ starts with $314159265358979323$" is equivalent to "there exists $k \in \mathbb N$ such that $314159265358979323 \cdot 10^k \le n < 314159265358979324 \cdot 10^k$". Can you show that the union of these intervals for all $k$ must contain infinitely many primes? –  Ilmari Karonen Aug 30 '11 at 22:34
3  
I am a little suspicious that two people asked the same question less than an hour apart. Can you give the source of the question? –  Qiaochu Yuan Aug 30 '11 at 23:04
    
@Sri: I certainly didn't read it as curt; I was merely saying that you can always suggest better titles (via the edit button) for questions whose titles are a bit short in the quality department... :) –  J. M. Aug 30 '11 at 23:07
add comment

4 Answers 4

We use the Prime Number Theorem, nothing else, and do all the details for a particular case. The method used can be easily transferred to the general case.

Let $\pi(x)$ be the number of primes that are less than or equal to $x$. For any real number $x>1$, let $F(x)=\dfrac{x}{\ln x}$. The Prime Number Theorem says that $$\lim_{x\to \infty}\frac{\pi(x)}{F(x)}=1.$$ By the definition of limit, given any positive $\epsilon$, we have $$1-\epsilon <\frac{\pi(x)}{F(x)} <1+\epsilon\qquad\text{(Inequality $1$)}$$ if $x$ is large enough. (The meaning of "large enough" depends on the value of $\epsilon$.)

We will show that there are infinitely many primes whose hexadecimal representation starts with $324$. Why $324$? The hexadecimal representation of $\pi$ starts with $3.24$. The OP used a much longer string of digits, also connected to $\pi$. But something of that length, in either hex or decimal, would be a nuisance to type. It seems appropriate to use initial "digits" of $\pi$, since we will be working with $\pi(x)$. Why hexadecimal? To show that the base does not matter. Also, the question originally came from a programming site! Why not use a general beginning and a general base? Because doing so might conceal the basic simplicity of the argument.

Important Note: In what follows, the numbers $324$ and $325$ appear often. They are always to be read as numbers to the base $16$. (So, for example, $324$ refers to the number which in base ten would be written as $804$.) The base $16$ occurs fairly often. Of course, it must be read in base ten! The few other numbers that appear, unless it is otherwise specified, are to be read as base $16$ numbers. Occasionally, for emphasis, the base is explicitly mentioned.

We want to show that there are arbitrarily large integers $n$ for which there is a prime $p$ with $$324_{16}\times 16^n <p < 325_{16}\times 16^n.$$ (The above inequality is equivalent to saying that the first three hexadecimal "digits" of $p$ are $3$, $2$, and $4$.)

By Inequality $1$, the number of primes less than $325\times 16^n$ is $>(1-\epsilon)F(325\times 16^n)$. Again by Inequality $1$, the number of primes less than $324\times 16^n$ is $<(1+\epsilon)F(324\times 16^n)$. So the number of primes in the interval ($324_{16}\times 16^n, 325_{16}\times 16^n)$ is greater than $(1-\epsilon)F(325\times 16^n) -(1+\epsilon)F(324\times 16^n)$. Thus if
$$(1-\epsilon)F(325\times 16^n) -(1+\epsilon)F(324\times 16^n)>0,$$ there must be at least one prime between our two bounds. (Recall that we are counting primes. If an inequality tells us the count is greater than $0$, that count is at least $1$.)

So we want to choose $n$ large enough so that Inequality $1$ is satisfied, and such that $$(1-\epsilon)\frac{325\times 16^n}{\ln(325\times 16^n)}>(1+\epsilon)\frac{324\times 16^n}{\ln(324\times 16^n)}.$$ The "laws of logarithms," together with some rearranging, show that the above inequality is equivalent to $$n(\ln 16)(1-649\epsilon)>(1+\epsilon)(324)(\ln 325)-(1-\epsilon)(325)(\ln 324)\qquad\text{(Inequality $2$)}$$ Note that $649$ is to be read in base $16$. Now we are ready for the final push.

First, let $\epsilon$ be the reciprocal of $1000_{16}$ (this reciprocal is safely less than the reciprocal of $649_{16}$).

Then on the left of Inequality $2$ we have $n$ times a positive constant, and on the right we have a constant. Next, let $n$ be large enough to ensure that Inequality $1$ is satisfied for our chosen value of $\epsilon$ and $x >324\times 16^n$.

Finally, let $n$ be also large enough to ensure that Inequality $2$ is satisfied for our chosen value of $\epsilon$. Then there is always a prime between $324_{16}\times 16^n$ and $325_{16}\times 16^n$, that is, a prime whose initial hexadecimal "digits" are $3$, $2$, and $4$.

Only minor editing changes are needed to make the argument work for any initial "digit" sequence, and any base.

share|improve this answer
    
+1 Very nice. A small nitpick. $315$ and $314$ are hex-digits, so $629$ is also in base-16. So, that particular choice of $\epsilon$ may not work... (Unless, of course, you meant $1000$ in base-16 as well :-)) –  Srivatsan Sep 3 '11 at 4:10
1  
@Srivatsan Narayanan: Thanks for pointing out the ambiguities. I have edited to make it (I hope) very clear which numbers are to be read in base $16$ and which are not. And yes, $1000$ is to be read in base $16$! –  André Nicolas Sep 3 '11 at 4:41
add comment

A simple consequence of the PNT is the fact that for any real number $k>1$ there exists an $n_0$ such that there is a prime between $n$ and $kn$ for all $n > n_0$. Now suppose your desired starting base-$b$ sequence is $d$ digits long; set $k = 1 + b^{-d}$ and apply the preceding fact.

share|improve this answer
    
+1 Sweet. A small nitpick. Since the question asks about a general base $b$ (not necessarily $10$) perhaps you can modify the $k$ to $1+b^{-d}$ to make the answer more accurate. –  Srivatsan Sep 3 '11 at 13:24
add comment

Use the prime number theorem to prove that there is an N such that for every M>N there is at least one prime that is written as 314159265358979323 followed by M other digits.

(Heuristically: There are $10^M$ possible numbers of this form, and the probability of each of them being prime is asymptotically proportional to 1/M -- thus the expected number of primes in each such interval grows towards infinity. Devising a rigorous argument from this sketch and one of the exact-bound versions of the prime number theorem is left as an exercise :-)

share|improve this answer
add comment

This is a special case of the following fact, a simple and short proof of which appears on p. 4 of Disjunctive sequences: An overview, by Calude, Priese and Staiger (1997):

  • If $a_1, a_2, a_3, \dots$ , is a strictly increasing infinite sequence of positive integers such that $\lim_{n \rightarrow \infty} (a_{n+1}/a_{n}) = 1$, then for any positive integer $m$ and any integer base $b ≥ 2$, there is some (and hence infinitely many) $a_n$ whose expression in base $b$ starts with the expression of $m$ in base $b$.

The desired result follows by taking $a_n$ to be the $n$th prime $p_n$, noting that the prime number theorem implies $p_n \sim n \ln n$, and hence that $\lim_{n \rightarrow \infty} (p_{n+1}/p_{n}) = 1$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.