2
$\begingroup$
How many prime numbers of $b$ bits are there?

Beyond the prime number theorem, one can give explicit bounds on the number of primes below some integer $n$, or in a given interval. For instance, Rosser and Schoenfeld [RS62, Corollary 3] prove:

For $λ≥20.5$, $\frac{3}{5}λ/\lnλ < π(2λ) - π(λ) < \frac{7}{5}λ/\ln(λ)$ where $π(x)$ denotes the number of primes $≤x$.

From this, one immediately derives that

For $b≥5$, the number of $b$-bit primes is between $\frac{3}{5\ln 2} 2^b/b \simeq 0.865⋅2^b/b$ and $\frac{7}{5\ln 2} 2^b/b\simeq 2.02⋅2^b/b$.

Experimentally for small values of $b$, one gets these values for $α = \frac{π(2^{b+1})-π(2^b)}{2^b/b}$:

$$\begin{array}{l|llllllllllllllllllllllllllllll} b& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ α & 1.00 & 1.00 & 0.750 & 1.25 & 1.09 & 1.22 & 1.26 & 1.34 & 1.32 & 1.34 & 1.37 & 1.36 & 1.38 & 1.38 & 1.39 & 1.39 & 1.39 & 1.40 & 1.40 & 1.40 & 1.41 & 1.41 & 1.41 & 1.41 & 1.41 & 1.41 & 1.41 & 1.41 & 1.42 & 1.42 \end{array}$$

My question is about explicit (and proven!) bounds that would be closer to the experimental data:

  • It seems that for $b≥4$, the value of $α$ is always $≥1$: Is it true and proved?
  • The value of $α$ seems to increase with $b$ from $b = 5$: Is it true and proved? False, cf. $b = 9$ or $b=12$ for instance.
  • Rosser and Schoenfeld prove that $α ≤ 2.02$: Are there improvements? Is $α ≤ 1.5$ true?

[RS62]: J. Barkley Rosser and Lowel Schoenfeld. Approximate formulas for some function of prime numbers. Illinois J. Math. 6(1): 64-94 (March 1962). DOI: 10.1215/ijm/1255631807.

$\endgroup$
3
  • 8
    $\begingroup$ PNT easily implies that $\frac{\pi(2x)-\pi(x)}{x/\log x}$ tends to $1$ as $1\to\infty$. For $x=2^b$ you will get that your $\alpha$ tends to $\frac{1}{\ln 2}\approx 1.442$. Any version of PNT with explicit error term should let you give explicit bounds on how fast it converges. This should easily answer first and third question. For the second one, note that your table itself contains two counterexamples, consider values at $b=8.9$ or $b=11,12$. The asymptotic behavior is less clear, and I'm not sure we should expect it's eventually monotone. $\endgroup$
    – Wojowu
    Nov 21, 2022 at 11:00
  • $\begingroup$ I have to say I am particularly embarrassed by my second question, added afterwards while it is clearly false... But actually, once you write it, your remark on the limit is obvious too! $\endgroup$
    – Bruno
    Nov 21, 2022 at 12:44
  • 1
    $\begingroup$ For $b\geq 31$, the value of $\alpha $ lies between $1.4$ and $1/\ln 2$. See my response below. $\endgroup$
    – GH from MO
    Nov 21, 2022 at 23:28

1 Answer 1

8
$\begingroup$

Dusart proved in his thesis that $$\frac{x}{\log x-1}<\pi(x)<\frac{x}{\log x-1.1},\qquad x\geq 60184.$$ It follows after a bit of calculation that $$0.975\frac{x}{\log x}<\pi(2x)-\pi(x)<\frac{x}{\log x},\qquad x\geq 2^{31}.$$ Hence for $b\geq 31$, the value of $\alpha$ lies between $0.975/\log 2\approx 1.4066$ and $1/\log 2\approx 1.4427$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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