I asked the question in Math StackExchange. Link: https://math.stackexchange.com/questions/4765476/approximation-of-partial-sum-over-prime-omega-function

I haven't got any response yet. Here are the details:

The prime omega function $\omega(n)$ counts the number of distinct prime factors of a natural number $n$, and can be defined as $\omega(n)=\sum_{p \mid n}1$. Let $S(N)=\sum_{n=1}^{N}n\omega(n)$. Let $\pi(n)$ denote the number of primes up to $n$.

$$\eqalign{S(N) &=\dfrac{1}{2}\sum_{\scriptstyle p{\text{ prime}} \atop \scriptstyle p\leq N} p\left(\left\lfloor\dfrac{N}{p}\right\rfloor ^2+\left\lfloor\dfrac{N}{p}\right\rfloor\right)\cr &\approx \dfrac{N\pi(N)}{2}+\dfrac{N^2}{2}\sum_{\scriptstyle p{\text{ prime}} \atop \scriptstyle p\leq N} \dfrac{1}{p}\cr &\approx \dfrac{N\pi(N)}{2}+\dfrac{N^2}{2}\left[\log \log N+M+o(1)\right],\cr}$$ where $M$ is the Meissel–Mertens constant.

The error term of this approximation is quite large. Is it possible to find a better approximation for this sum?

A better approximation for the sum of reciprocal primes (see https://arxiv.org/pdf/1703.08032.pdf) does not help to improve the overall sum.

The following approximation seems to work well. $$\tilde{S}(N,\epsilon)=\left[\dfrac{N\pi(N)}{2}+\dfrac{N^2}{2}\left(\log \log N+M\right)\right]\cdot \left(1+\dfrac{1}{(\log N)^{1+\epsilon}}\right)^{-1}$$, where $\epsilon \in (0,1)$. Define the percentage error as $E(N,\epsilon)=\left |\dfrac{S(N)-\tilde{S}(N,\epsilon)}{S(N)}\right |\times 100$. The following table gives an idea as to how well the approximation works for $\epsilon=\dfrac{2}{5}$.

$N$ $S(N)$ $E\left(N,\frac{2}{5}\right)$
$10^3$ $1104960$ $0.192894816907$
$10^4$ $124547620$ $0.0961202670514$
$10^5$ $13558020500$ $0.0234415251444$
$10^6$ $1446379298344$ $0.00741488319826$
$10^7$ $152305298038685$ $0.0118235266249$
$10^8$ $15895296473923817$ $0.00880016331673$
$10^9$ $1648198262567978862$ $0.00327960320611$
$10^{10}$ $170070011690546177056$ $0.00270740071241$
  • 2
    $\begingroup$ Perhaps you can use the Erdős–Kac theorem. If you treat $\omega(n)$ as a random variable with mean and variance $\log \log n$, you get a sum of normal variables with mean and variance $n \log \log n$, so the total sum is a normal variable with mean and variance $\sum_{i=1}^n {i \log \log i}$, so you'd expect the number to be around $\sum_{i=1}^n {i \log \log i} \pm \sqrt{\sum_{i=1}^n {i \log \log i}}$. This is mostly heuristic, I don't know if assuming these are independent can be justified $\endgroup$ Sep 26 at 3:52
  • $\begingroup$ @CommandMaster Thanks! I was not aware of this theorem. I shall try to get a better estimate using this. $\endgroup$
    – piepie
    Sep 26 at 3:56
  • $\begingroup$ My comment is inaccurate, the variance is actually $i^2 \log \log i$, but it should still give an error term of $\tilde O(n^{1.5})$ if it is correct $\endgroup$ Sep 26 at 4:02
  • 1
    $\begingroup$ @Charles there is another error term, since $\lfloor \frac n p \rfloor^2 = (\frac n p + O(1))^2 = (\frac n p)^2 + O(\frac n p)$ $\endgroup$ Sep 26 at 4:04
  • $\begingroup$ Assuming RH I can show this sum is $\frac12N^2\sum_{p\leq\sqrt N}\frac1p+\sum_{i\leq\sqrt N\\p\text{ prime}}{i (\text{li}(\frac{N^2}{i^2}) - \text{li}(N))}+O( N^{1.75 + \epsilon})$, but I'm not sure how to estimate the left part of the sum. $\endgroup$ Sep 26 at 5:38

2 Answers 2


By partial summation, one has $$ S(N) = N\sum_{n=1}^N \omega(n) - \int_{1}^N \bigg(\sum_{n\leq t} \omega(n)\bigg) dt. $$ Using Mertens' theorem with the classical error term in the prime number theorem, one has, for some constant $c > 0$, $$ \begin{aligned} \sum_{n=1}^N \omega(n) = \sum_{p\leq N} \Big\lfloor \frac{N}{p}\Big\rfloor &= N \sum_{p\leq N} \frac{1}{p} - \sum_{p\leq N} \left\{ \frac{N}{p}\right\} \\ &= N \Big(\log\log N + M + O\Big(\exp\big(-c\sqrt{\log N}\big) \Big) \Big)- \sum_{p\leq N} \left\{ \frac{N}{p}\right\} \end{aligned} $$ where $\{\cdot\}$ denotes the fractional part. The sum of fractional parts can evaluated using Proposition 3 of this paper, and we have $$ \sum_{p\leq N} \left\{ \frac{N}{p}\right\} = \int_{2}^N \frac{\left\{N/t \right\}}{\log t} dt + O\Big(\exp\big(-c(\log N)^{3/5-\varepsilon}\big) \Big). $$ By Proposition 2 of the above paper, the integral can be expanded asymptotically into a sum with descending powers of $\log N$: for any $k\geq 1$, $$ \int_{2}^N \frac{\left\{N/t \right\}}{\log t} dt = c_0 \frac{N}{\log N} + c_1 \frac{N}{(\log N)^2} + \cdots + c_k \frac{N}{(\log N)^k} + O_k\left( \frac{N}{(\log N)^{k+1}}\right). $$ I leave the remaining details of the calculations to you, but this roughly shows that you should not hope for an error term better than $O_k\left( \frac{N^2}{(\log N)^k}\right)$ in your asymptotic expansion.

  • 1
    $\begingroup$ Thanks for your answer. I came up with an empirical approximation that works really well for large $N$. I have no idea how to prove it though. $\endgroup$
    – piepie
    Sep 26 at 6:39
  • 3
    $\begingroup$ The Wikipedia page en.wikipedia.org/wiki/Prime_omega_function has a similar expansion for the mean value of $\omega$, which can be converted into the above sort of expansion by summation by parts. $\endgroup$
    – Terry Tao
    Sep 27 at 1:05
  • $\begingroup$ @TerryTao, Thank you Prof. Tao for providing the solution idea. I shall look into the cited paper. $\endgroup$
    – piepie
    Sep 27 at 2:41

As Prof. Tao suggested, we can estimate $S(n)$ using Summation by parts method. $$S(n)\sim nf(n) - \sum_{k=2}^{n-1}f(k),$$ where $f(n)$ approximates the sum $\sum_{k=1}^{n}\omega(k)$. $$\sum_{k=1}^{n}\omega(k) \sim f(n) = n \left[ \log \log n + M + \sum _{k\geq 1}\left(\sum _{j=0}^{k-1}\frac{\gamma_j}{j!} - 1\right)\frac{(k-1)!}{(\log n)^k}\right],$$ where $M$ is the Meissel-Mertens constant and $\gamma_j$s are Stieltjes constants.

Let $T(n)=\sum_{m=2}^{n}f(m)$. We can estimate $T(n)$ using Euler-Maclaurin formula. $$T(n)\sim \int_{2}^{n}f(x) dx + \frac{1}{2}\left(f(n)+f(2)\right) + \sum_{k=1}^{\infty}\frac{B_{2k}}{(2k)!}\left(f^{(2k-1)}(n)-f^{(2k-1)}(2)\right),$$ where $B_k$ is the $k^{th}$ Bernoulli number (with $B_1=\frac{1}{2}$).

Following this approach we get the following estimates (denoted by $\hat{S}(n)$) for $S(n)$ using $5$ terms in the summatory part of $f(.)$.

$N$ $S(N)$ $\hat{S}(N)$ Percentage error
$10^3$ $1104960$ $1104744.867385$ $0.019470$
$10^4$ $124547620$ $124548871.265378$ $0.001005$
$10^5$ $13558020500$ $13559354294.383795$ $0.009838$
$10^6$ $1446379298344$ $1446466799145.233356$ $0.006050$
$10^7$ $152305298038685$ $152311928057871.725336$ $0.004353$
$10^8$ $15895296473923817$ $15895763172409493.954120$ $0.002936$
$10^9$ $1648198262567978862$ $1648231275071905930.713382$ $0.002003$
$10^{10}$ $170070011690546177056$ $170072396183761800450$ $0.001402$
$10^{11}$ $17482087123791069603605$ $17482264536463768138654$ $0.001015$

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.