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.

Improve this question
$\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
    Commented 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
    Commented 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
    Commented Nov 21, 2022 at 23:28

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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