# Counting semiprimes

The prime-counting function $\pi(n)$ returns the number of prime numbers less than or equal to $n$. The prime number theorem gives the asymptotic behaviour $\pi(n)\sim n/\log n$.

We shall call a number semiprime if it is the product of two primes. Let $\omega(n)$ denote the semiprime-counting function. What is the asymptotic behaviour of $\omega(n)$? I claim that

$\omega(n) \sim \frac{n}{\log n} \log\left( \frac{\log n}{\log 2} \right)$

Edit (17 September 2016) Based on experiments in Mathematica, the above seems to be a lower bound, while an upper bound is given by

$\omega(n) \sim \frac{n \log \log n}{\log n}$

I obtain these by the following heuristic, probabilistic argument. The probability that a random integer chosen between 1 and $n$ is $\pi(n)/n \sim 1/\log n$; loosely, this means that the probability of a randomly chosen large number $n$ is approximately $1/\log n$. Similarly, $\omega(n) / n$ is the probability that a randomly-chosen $m < n$ is semiprime.

An exact formula for $\omega(n)$ is

$\omega(n) = \sum_{x=2}^{n/2} \sum_{y=2}^{n/x} 1(xy \text{ is prime}) = \frac{1}{2} \sum_{x=2}^{n/2} \sum_{y=2}^{n/x} 1(x \text{ is prime}) 1(y \text{ is prime}).$

The sum over $y$ is trivially $\pi(n/x) \sim (n/x)/(\log n - \log x)$. Hence

$\omega(n) \sim \sum_{x=2}^{n/2} 1(x \text{ is prime}) \frac{n}{x (\log n - \log x)}.$

We split the sum at $x = \sqrt n$ into two parts, and assume that the first part is dominated by the second. In the second part, $x$ is large and we invoke $1(x \text{ is prime}) \sim 1/\log x$ and approximate the sum as an integral, to get

$\omega(n) \sim \int_{\sqrt n}^{n/2} \frac{n}{x \log x (\log n - \log x)} dx.$

Evaluating the integral and keeping only the highest-order terms, we get the desired formula.

The semiprime-counting function can be implemented in Mathematica by

SemiprimeQ[n_] := SemiprimeQ[n] = Module[{f},
f = FactorInteger[n];
(
((Length[f] == 2) && (Total[Last /@ f] == 2))
|| ((Length[f] == 1) && f[[1]][[2]] == 2) )
];

w[n_] := w[n] = Length[Select[Range[n], SemiprimeQ]]


(where we memoise the results to speed things up). The following code produces a graph showing the validity of these approximation:

W1[n_] := n/Log[n] Log[Log[n]];
W2[n_] := n/Log[n] Log[Log[n]/Log[2]];
nn = 150000; nj = 500;
Show[
ListPlot[Table[{n, w[n]/W1[n]}, {n, 1, nn, nj}],
PlotStyle -> Red],
ListPlot[Table[{n, w[n]/W2[n]}, {n, 1, nn, nj}],
PlotStyle -> Green]
]


This site uses Akismet to reduce spam. Learn how your comment data is processed.