# Asymptotic density of k-almost primes

Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is $$\pi_k(x)\sim\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\qquad\qquad(1)$$ but this approximation is very poor for $k>1$.

For $\pi(x)$ much more is known. A (divergent) asymptotic series $$\pi(x)=\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2}{\log^2x}+\frac{6}{\log^3x}\cdots\right)\qquad\qquad(2)$$ exists (see. e.g., the historical paper of Cipolla [1] who inverted this to produce a series for $p_n$). And of course it is well-known that $$\pi(x)=\operatorname{Li}(x)+e(x)\qquad\qquad(3)$$ for an error term $e(x)$ (not sure what the best current result) that can be taken [4], on the RH, to be $O(\sqrt x\log x)$. Even better, Schoenfeld [6] famously transformed this into an effective version with $$|e(x)|<\sqrt x\log x/8\pi\qquad\qquad(4)$$ for $x\ge2657$. For the heretics rejecting the Riemann Hypothesis, Pierre Dusart has a preprint [2] which improves on the results in his thesis [3]; in particular, for $x\ge2953652302$, $$\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2}{\log^2x}\right)\le\pi(x)\le\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2.334}{\log^2x}\right)\qquad\qquad(5)$$

But I know of no results even as weak as (2) for almost primes. Even if nothing effective like (5) exists, I would be happy for an estimate like (3).

## Partial results

Montgomery & Vaughan [5] show that $$\pi_k=G\left(\frac{k-1}{\log\log x}\right)\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\left(1+O\left(\frac{k}{(\log\log x)^2}\right)\right)$$ for any fixed k (and, indeed, uniformly for any $1\le k\le(2-\varepsilon)\log\log x$ though the O depends (exponentially?) on the $\varepsilon$), where $$G(z)=F(1,z)/\Gamma(z+1)$$ and $$F(s,z)=\prod_p\left(1-\frac{z}{p^s}\right)^{-1}\left(1-\frac{1}{p^s}\right)^z$$ though I'm not quite sure how to calculate $F$.

If this is the best result known (rather than simply the best result provable at textbook level) then this shows that far less is known about the distribution of, e.g., semiprimes than about primes.

## References

[1] M. Cipolla, “La determinazione assintotica dell n$^\mathrm{imo}$ numero primo”, Matematiche Napoli 3 (1902), pp. 132-166.

[2] Pierre Dusart, "Estimates of Some Functions Over Primes without R.H." (2010) http://arxiv.org/abs/1002.0442

[3] Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres premiers" (1998) http://www.unilim.fr/laco/theses/1998/T1998_01.html

[4] Helge von Koch, "Sur la distribution des nombres premiers". Acta Mathematica 24:1 (1901), pp. 159-182.

[5] Hugh Montgomery & Robert Vaughan, Multiplicative Number Theory I. Classical Theory. (2007). Cambridge University Press.

[6] Lowell Schoenfeld, "Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x). II". Mathematics of Computation 30:134 (1976), pp. 337-360.

[7] Robert G. Wilson v, Number of semiprimes <= 2^n. In the On-Line Encyclopedia of Integer Sequences, A125527. http://oeis.org/A125527 ; c.f. http://oeis.org/A007053

EDIT, by Joël. I edit this old question to bump it up and observe that one aspect has not been answered. Namely, is there under the Riemann Hypothesis an asymptotic estimate for $\pi_k(x)$ analog to (3), (4) for $\pi(x)$ (that is $\pi(x) = Li(x) + O(\sqrt{x} \log x)$)? Or any estimate for $\pi_k(x)$, with a principal term given by some classical functions, and an error term in $O(x^\delta)$ with some $\delta<1$? Micah's answer gives a principal term which is a rational function of $x$, $\log x$, $\log \log x$, but with a much less good error term, which is not surprising since even for $\pi(x)$ it is well-known that the principal term must be written as $Li(x)$, not $x/\log(x)$, if we want to have some hope of and rarer term in $O(x^\delta)$, $\delta<1$ (let alone $O(\sqrt{x}\log x)$).

-
Multiplicative number theory I : classical theory  Hugh L. Montgomery, Robert C. Vaughan.  Cambridge University Press, 2007. – Will Jagy Aug 18 '10 at 5:27
@Will, in particular, Section 7.4, Numbers composed of a prescribed number of primes. The formulas are too complicated to fit within the margins of this comment! – Gerry Myerson Aug 18 '10 at 5:59
I copied out a number of pages, around here somewhere. The raw facts alluded to, perhaps with less detail, are in Hardy and Wright, section 22.18 – Will Jagy Aug 18 '10 at 6:42
@Will: I don't see anything more than (1) -- Theorem 437 in my printing -- in H&W. Am I missing something? – Charles Aug 18 '10 at 7:07
Can you, please, eliminate all instances of the adjective "masterful" from your question? Not only is its utility questionable, it creates an impression that you are trying to promote certain papers. – Victor Protsak Aug 18 '10 at 19:10

I'll address Joel's edited question of getting good asymptotics on RH. The argument below is essentially due to Selberg, but this is not quite what he does and I haven't seen it presented this way in the literature. The natural problem is to consider the coefficients of $(\log \zeta (s))^k/k!$ rather than numbers with exactly $k$ prime factors. Note that for $k=1$ and $2$ the two objects are closely related, and some obvious but unpleasant combinatorics is needed for larger $k$.

Thus we want to compute $$\frac{1}{2\pi i} \frac{1}{k!} \int_{c-i\infty}^{c+i\infty} (\log \zeta(s))^k x^s \frac{ds}{s},$$ where the integral is taken over some line with $c>1$. Now we want to shift contours as usual, but we need to be careful because logarithmic singularities are involved rather than just poles. First choose $c$ just a little bigger than $1$ and truncate the integral at some height $T$. Then deform the contour as follows: Take a slit along the real axis from $1/2+\epsilon$ to $1$ with a line just above and a line just below the slit, and then line segments from $1/2+\epsilon$ to $1/2+\epsilon +iT$ and then from there to $c+iT$, and similar line segments below the real axis. If one assumes RH, the errors in truncation together with all the integrals except for the ones above and below the slit can be bounded by $x^{1/2+\epsilon}$. Thus we conclude that our integral equals, with error $O(x^{1/2+\epsilon})$, $$-\frac{1}{2\pi i} \frac{1}{k!} \int_{1/2+\epsilon}^{1} \Big((\log \zeta(\sigma+ 0^+ i))^k - (\log \zeta(\sigma+0^- i))^k \Big) \frac{x^\sigma}{\sigma} d\sigma.$$ Here I use $0^+i$ to denote the upper part of the slit, and $0^-$ to denote the lower part. The two terms don't cancel out because of the change in the argument of $\zeta$ above and below the slit. Note that above the slit one has $\log \zeta(\sigma+0^+i) = \log |\zeta(\sigma)| - i\pi$ and below the slit one has $\log \zeta(\sigma+0^-i) = \log |\zeta(\sigma)| +i \pi$. Thus we find that the desired answer is $$\frac{1}{\pi k!} \int_{1/2+\epsilon}^1 \text{Im} (\log |\zeta(\sigma)| +i\pi)^k \frac{x^{\sigma}}{\sigma} d\sigma + O(x^{1/2+\epsilon}).$$

To appreciate what this means, consider first the prime number theorem which is the case $k=1$. From above we see that the main term is $$\int_{1/2+\epsilon}^{1} \frac{x^{\sigma}}{\sigma} d\sigma,$$ and a change of variables produces $\text{Li}(x)$. When $k=2$ (essentially the case of $\pi_2(x)$) the work above gives $$\int_{1/2+\epsilon}^1 \log |\zeta(\sigma)| \frac{x^{\sigma}}{\sigma} d\sigma + O(x^{1/2+\epsilon}).$$ The leading order asymptotics come from $\sigma$ very close to $1$, on the scale of $1-c/\log x$, and then $\log |\zeta(\sigma)|$ will contribute the extra $\log \log x$. One can obtain more precise asymptotic expansions etc from this expression.

Let me also note that one can make this argument unconditional using the classical zero free region, and it may be worthwhile carrying this out. The usual way in which such results are carried out in the literature is to start with asymptotics for coefficients of $\zeta(s)^z$ for complex $z$, and then to use the saddle point method to identify from this numbers with $k$ prime factors. This is Selberg's argument with various elaborations, most notably by Hildebrand and Tenenbaum. The argument above seems to be a shortcut and may produce better results. It would be surprising if nobody had thought of it before, but at any rate I haven't seen it.

-
Wow! Thanks Lucia, that looks wonderful. I am growing more and more curious to know who you are in real life... – Joël Oct 31 '13 at 12:44

In Tenenbaum's book "Introduction to analytic and probabilistic number theory" he uses the Selberg-Delange method to prove that the estimate

$$\pi_k(x):=\sum_{n\leq x, \ \omega(n)=k} 1 = \frac{x}{\log x} \sum_{j=0}^N \frac{P_{j,k}(\log\log x)}{(\log x)^j} + O_A\left(\frac{x(\log\log x)^k}{k! \log x} R_N(x) \right)$$

holds uniformly for $x\geq 3$, $1\leq k \leq A \log \log x$, and $N\geq 0$ where $P_{j,k}$ is a polynomial of degree at most $k-1$,

$$R_N(x) = e^{-c_1\sqrt{\log x}} + \left(\frac{c_2 N+1}{\log x}\right)^{N+1},$$

and $c_1$ and $c_2$ are positive constants which may depend on $A$. This is Theorem 4 of Chapter 6.

In Theorem 5, he shows that a similar estimate holds for $\displaystyle{N_k(x):=\sum_{n\leq x, \ \Omega(n)=k} 1}$.

-
Thank you very much! Is there a version of this result for $\sum_{n\le x,\Omega(n)=k}$ which I think Tenenbaum calls $\tau_k$? And is there a method for determining the polynomials? – Charles Aug 19 '10 at 6:29
The theorem is essentially the same for $\sum_{n\leq x, \Omega(n)=k}$, except that the polynomials are (possibly) different. It seems possible that you could determine the polynomials for small $k$. – Micah Milinovich Aug 19 '10 at 11:35
For $\Omega(n)$ the result holds only when $A<2$. For $A\ge2$ the behaviour changes due to the effect of powers of 2 and Nicolas has obtained an asymptotic in the full range of $k$. (Sur la distribution des nombres entiers ayant une quantit ́e fix ́ee de facteurs premiers. Acta Arith., 44(3):191–200, 1984.) – Dimitris Koukoulopoulos Jan 18 '14 at 17:53

According to Dickson's History, Gauss, in a manuscript of 1796, stated empirically that the number $\pi_2(x)$ of integers $\le x$ which are products of two distinct primes, is approximately $x\log\log x/\log x$. Landau proved this result and the generalization $$\pi_{\nu}(x)={1\over(\nu-1)!}{x(\log\log x)^{\nu-1}\over\log x}+O\left({x(\log\log x)^{\nu-2}\over\log x}\right)$$ where $\pi_{\nu}(x)$ is the number of integers $\le x$ which are products of $\nu$ distinct primes. So that would be the status quo, as of 1919.

EDIT. Noting John's answer, and not having Tenenbaum's book, I looked for relevant papers by Tenenbaum, and found Adolf Hildebrand and G${\rm\acute e}$rald Tenenbaum, On the number of prime factors of an integer, Duke Math J 56 (1988) 471-501, MR89k:11084. The authors prove what the reviewer
(${\rm Aleksandar\ Ivi\acute c}$) calls a "remarkable asymptotic formula" for $\pi(x,k)$, the number of integers up to $x$ with exactly $k$ distinct prime factors. I don't have the energy to reproduce the lengthy formula here (nor the nerve to just cut'n'paste it from Math Reviews).

Another paper that looks like it may be of interest is Hsien-Kuei Hwang, Sur la repartition des valeurs des fonctions arithmetiques, J No Thy 69 (1998) 135-152, MR99d:11100. The author claims to completely characterize the asymptotic behavior of the number of positive integers up to $x$ with $m$ prime factors (counted with multiplicities).

-
I suppose that speaks to why the error is so bad -- it's off by (1 + O(1/log log x) instead of (1 + O(1/log x)) as in the case of the prime-counting function. – Charles Aug 18 '10 at 7:11
The Hildebrand & Tenenbaum paper is very good, thanks for the pointer. It gives good insight into why different cases are different. Unfortunately it's focused on improving the range of admissible $k$-values, which don't really concern me -- I care mostly about the case k = 2. I've downloaded the Hwang paper and have been reading through it (slowly; my French is passable but not good by any means). – Charles Aug 19 '10 at 17:08

I looked at $$\int_e^x\frac{(\log\log t)^{k-1}}{(k-1)!\log t}dt$$ to see if, empirically, the error was any less in the special case $k = 2,\ x = 2^n$ (semiprimes at powers of 2, as in A125527). Unfortunately the results were inconclusive. The error was smaller over the domain I checked: about half the error around a million, tapering down to a quarter less error at $2^{49}$. But everywhere I checked both estimates were too small, by significant relative factors.

Further, these errors did not seem to taper off much. The error in $x\log\log x/\log x$ went from 10% to 8% fairly smoothly, while the error in the integral reached an apparent relative maximum around $2^{40}$, staying between 5% and 6% the whole way. This seems fundamentally unlike the behavior with Li and $x/\log x$ where the error in the latter (wrt $\pi(x)$) quickly outpaces the error in the former.

-

This doesn't help, but it may entertain

-

The Wolfram MathWorld page for "Semiprime" ($k=2$) at http://mathworld.wolfram.com/Semiprime.html gives the following formula:

"A formula for the number of semiprimes less than or equal to $n$ is given by

$$\pi_2(x) = \sum_{k=1}^{\pi(\sqrt{x})} [\pi(x/p_k)-k+1],$$

where $\pi(x)$ is the prime counting function and $p_k$ is the $k$-th prime (R. G. Wilson V, pers. comm., Feb. 7, 2006; discovered independently by E. Noel and G. Panos around Jan. 2005, pers. comm., Jun. 13, 2006)."

Curiously, the number of terms in the above sum, $\pi(\sqrt{x})$, is approximately $\operatorname{Li}(\sqrt{x})$, which is the order of the main error term in the formula $\pi(x) = \operatorname{Li}(x) + e(x)$ itself. Further, the value of $\pi(x/p_k)$ in the final term is also equal to $\pi(x/\sqrt{x}) = \pi(\sqrt{x})$.

Here is a follow-up question: Has there been any research about the distribution of primes and semiprimes together? One would expect the error term to be smaller than for either primes or semiprimes alone, because a region with fewer primes will tend to have more semiprimes, and vice versa.

-

As not necessarily proven results were asked for, I have found the following quite accurate:

$$N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid \ \sim \Re\bigg(\frac{2^{1-k}\alpha e^{1+e}x\log(1+e+\log(2^{1-k}\alpha x))^{\beta}}{\beta!(1+e+\log(2^{1+e}\alpha x)}\bigg)$$ for $1 \leq k\leq \lfloor \log_2 (x) \rfloor$, where $\log_2$ is $\log$ base $2$, $\gamma$ is Euler's constant, $\beta=1+e+ \log \alpha +(1+e+ \log \alpha) ^{1/\pi}$, and$$\alpha=\frac{1}{2}\ \rm{erfc}\bigg(-\frac{k-(2e^{\gamma}+\frac{1}{4})}{(2e^{\gamma}+\frac{1}{4})\sqrt{2}\ }\bigg)-2\rm{T}\bigg(\bigg(\frac{k}{(2e^{\gamma}+\frac{1}{4})}-1\bigg),e^{\gamma}-\frac{1}{4}\bigg)\\$$ where $\rm{erfc}$ is the complementary error function and $\rm{T}$ is the Owen T-function.

In integral form, $$\alpha= \frac{1}{\pi}\int_{(-3+8e^\gamma)/(\sqrt{2}(1+8e^\gamma))}^\infty e^{-t^2}\rm{d} t +\int_0^{1/4\ -\ e^\gamma}\frac{e^{-(3\ -\ 8e^\gamma)^2(1+t^2)/(2(1+8e^\gamma)^2)}}{1+t^2}\rm{d} t.$$

As $k\rightarrow \infty$, $\alpha\rightarrow 1$, so

$$\lim_{k \rightarrow \infty}N_{k}(x \cdot 2^{k-1})\sim\frac { {e^{e+1}} x\log\log( {e^{e+1}} x)^{\beta}}{\log( {e^{e+1}} x)\beta!},$$ where $\beta=\log(e^{e+1})+\log(e^{e+1})^{1/\pi}.$

For $k\leqslant 3$, improvements to the above can certainly be made, but as $k\rightarrow \infty$ (or more correctly, as $k\rightarrow \lfloor \log_2 (x) \rfloor$), the formulae above, as far as have been tested, seem to be fairly accurate.

For convenience, I include the following Mathematica code:

cdf[k_, x_] :=
Re[N[
(2^-k E^(1 + E) x Log[1 + E + Log[2^-k x (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])]]^(1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] +4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])] + (1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])])^(1/\[Pi])) (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma]))/((1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])] + (1 + E + Log[1/2 (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2]
(1 + 8 E^EulerGamma))] + 4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma),
1/4 - E^EulerGamma])])^(1/\[Pi]))!
(1 + E + Log[2^-k x (Erfc[(1 + 8 E^EulerGamma - 4 k)/(Sqrt[2] (1 + 8 E^EulerGamma))] +
4 OwenT[(1 + 8 E^EulerGamma - 4 k)/(1 + 8 E^EulerGamma), 1/4 - E^EulerGamma])]))]];

landau[k_, x_] := N[(x Log[Log[x]]^(-1 + k))/((-1 + k)! Log[x])];

actual[k_, x_] := N[Sum[1, ##] & @@ Transpose[{#, Prepend[Most[#], 1], PrimePi@
Prepend[ Prime[First[#]]^(1 - k) Rest@FoldList[Times, x, Prime@First[#]/Prime@Most[#]],
x^(1/k)]}] &@Table[Unique[], {k}]];


I warmly welcome any criticism or comments on the above, and apologise in advance if I have made any serious errors.

Note: Table code included as requested:

a = 7;
x = 10^a;
kk = 20;
TableForm[Transpose[{Table[x, {x, 1, kk}], Table[Round[landau[k, x]], {k, 1, kk}],
Table[Round[cdf[k, x]], {k, 1, kk}], Table[actual[k, x], {k, 1, kk}]}],
TableHeadings -> {None, {"k  ", "Landau", "CDF   ", "Actual"}},
TableSpacing -> {2, 3, 0}]

-
I notice in your ArXiv article that you use data up to 10^ 7. How do your parameters change if you perform the same analysis, but take the 7 and change it to 8? And then to 9? – The Masked Avenger Jan 18 '14 at 17:27
I have included the code so you can try it. It seems fairly consistent. I will include the code I used to generate the table also (see above) if that helps - just change the a=7 to whatever you want to test. – martin Jan 18 '14 at 17:30
Obviously the higher you go, the longer it takes to calculate. It was not really the low $k$ that I was interested in (as there is not much difference with Laundau for these), but the higher $k$ that approached $\lfloor \log_2 (x)\rfloor$. Mathematica obviously calculates these far quicker, ie, if {k, 1, kk} is changed to {k, 7, kk}, for example. – martin Jan 18 '14 at 17:37
NB I would be interested to know how you go with the tests :) – martin Jan 18 '14 at 17:39
@draks...It was my first attempt at something like this, so take it with a pinch of salt as is largely heuristic: link. – martin Sep 11 '14 at 6:03