Let $$D_2(n) =\sum_{pq\leq n} 1,$$ and $$F_2(n) =\sum_{pq\leq n} \frac{1}{pq}$$ where $p,q$ are primes. Similarly define $$D_k(n) =\sum_{p_1\cdots p_k\leq n} 1,$$ and $$F_k(n) =\sum_{p_1\cdots p_k\leq n} \frac{1}{p_1\cdots p_k}.$$

I believe my calculations showing $$F_2(n)\sim \frac{(\log\log n)^2}{2}$$ and $$D_2(n)\sim \frac{n \log\log n}{\log n}$$ are correct (I used PNT and Mertens theorems).

What about larger $k$?

Is it possible to allow $k$ to grow very slowly and still get an estimate?

  • 1
    $\begingroup$ Actually the answer that was posted here (and now deleted), brief though it was, did answer your question. The Selberg-Delange method gives asymptotics for $D_k(n)$ in a wide range of $k$, and partial summation gives the other sum. Look this up in a Tenenbaum's book, or Montgomery-Vaughan. $\endgroup$
    – Lucia
    Dec 2, 2016 at 5:19

2 Answers 2


For any fixed $k \geq 1$, one has $$D_k(n) \sim \frac{x}{\log x} \frac{(\log \log x)^{k-1}}{(k-1)!}.$$ This was originally proved by Landau in 1909 using induction of $k$.

For $k \ll \log \log x$, see Theorem 4 of chapter 6 of Tenenbaum's book "Introduction to analytic and probabilistic number theory." This is the Selberg-Delange method.

One can get decent upper bounds uniformly in $k$ with elementary methods, see for instance page 4 of these notes.

There is a nice heuristic: note the above assymptotic suggests a Poisson distribution with parameter $\log \log x$. One can view the events $\{ p | m\}_{p}$ as weakly dependent events with probability of success about $1/p$. So by general principles of probability (section 4.7 of Sheldon Ross' book) suggest that the probability of $k$ successes is modeled by a Poisson distribution. The shift in the index $k$ comes from the fact that every integer has at least one prime factor.


Define the function $F^*(n)=\underset{p_1\dots p_k\leq n}{\sum_{p_, \ldots, p_k}}\frac{1}{p_1\dots p_k}$. Then we have for each fixed $k$ the asymptotics $F_k^*(n)\sim(\log\log n)^k$. To see this note the obvious upper and lower bounds $$ \left(\sum_{p\leq n^{1/k}}\frac{1}{p}\right)^k\leq F_k(n)\leq \left(\sum_{p\leq n}\frac{1}{p}\right)^k, $$ and use the asymptotics $\sum_{p\leq n}\frac{1}{p}\sim\log\log n$.

To deduce an asymptotics for $F_k(n)$, note first that summands in $F_k^*$ corresponding to tuples which are not pairwise different are negligible, in fact, using a variation of the upper bound above we see that this contribution is $\mathcal{O}((\log\log n)^{k-1})$. If the primes are pairwise different, then the corresponding summand occurs $k!$-times in $F_k^*$ and only once in $F_k$, thus $F_k(n)\sim\frac{1}{k!}(\log\log n)^k$, confirming your computation.

As $k$ grows, we use the bound $\sum_{p\leq n}\frac{1}{p}=\log\log n +\mathcal{O}(1)$, thus $F_k^*(n)=(\log\log n)^k+\mathcal{O}(k(\log\log n)^{k-1})$. Deleting tuples which contain the same prime multiple times gets more complicated. A crude estimate would be $B_k(\log\log n)^{k-1}<k^k(\log\log k)^{k-1}$, where $B_k$ denotes Bell numbers. In this way you get a uniform bound almost up to $k=\log\log\log n$. If you need better estimates, you would have to consider partitions more carefully, which is doable, but some work.


Your Answer

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

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