# $\sum_{p\leq n}\sum_{q\leq N}\sum_{n\leq N;p|n,q|n}1=^? \sum_{pq \leq N}\big( \frac N{pq}+O(1)\big)+\sum_{p \leq N}\big( \frac N{p}-\frac N{p^2}\big)$

I was studying Marius Overholt 'A course in Analytic Number Theory'. There in the section of "Normal order method". The proposition he is going to prove is

$Var[w]=O(loglog(N))$ where $w(n)$ is the no of prime divisors of $n$.

pf: We have $\sum_{n\leq N}w^2(n)=\sum_{n\leq N}\big(\sum_{p| n}1\big)\big(\sum_{q| n}1\big)=\color{red}{\sum_{p\leq N}\sum_{q\leq N}\sum_{n\leq N;p|n,q|n}1=^? \sum_{pq \leq N}\big( \frac N{pq}+O(1)\big)+\sum_{p \leq N}\big( \frac N{p}-\frac N{p^2}\big)}$

I am not getting how to get the red lined equality. Please help.

• Could you check your notations? I feel that at least the first line should be $p|n$, $q|n$ instead of $N$. – Hw Chu Feb 20 '18 at 18:47
• You are absolutely right. I am sorry for the typos. – user533344 Feb 20 '18 at 18:52

## 1 Answer

Split into two cases: $p \neq q$ and $p = q$.

If $p \neq q$, $p|N$, $q|N$ give you $\lfloor \frac N{pq}\rfloor = \frac N{pq} + O(1)$ numbers satisfying the condition $n \leq N$, $p | n$, $q | n$. As long as $pq \leq N$ you will get at least one number and thus should be included in your summand. Note that $pq$ and $qp$ will be counted twice if $p \neq q$.

If $p = q$ things are different. If $p \leq N$ you will have $\lfloor \frac N{p}\rfloor = \frac N{p} + O(1)$ numbers satisfying the condition $n \leq N$, $p | n$, $q | n$. But the first summand this is already counted as $\lfloor \frac N{p^2}\rfloor$ so you should compensate it with a $\frac Np - \frac N{p^2}$.

• would you please look at this too math.stackexchange.com/questions/2659093/… – user533349 Feb 20 '18 at 19:23
• Sorry, I read it, but I am not even sure if you are on the right track, so I do not know if that equation is valid. – Hw Chu Feb 20 '18 at 19:29