3
$\begingroup$

I feel like an idiot for asking this, so bear my stupidity.

I have the sum $\sum_{n\leq N} \sum_{p | n ; \ p \ prime} 1$, and I want to change the order of summation of these two sums I think it should be:

$\sum_{n | N} \sum_{p\leq n ; \ p \ prime} 1 = \sum_{n | N} \pi(n)$

Is this right or wrong, in which case if it's right then how do I simplify the term $\sum_{n\mid N}\pi(n)$ any further? Here $\pi(n)$ is the prime-counting function.

Thanks in advance.

  • 1
    I don't $s$ee where you changed the order of summation..2012-07-05

1 Answers 1

4

It looks like your answer is wrong.

The correct change is:

$$\sum_{n\leq N} \sum_{\substack p|n \\ p \text{ prime}} 1= \sum_{\substack p\leq N \\ p\text{ prime}} \sum_{\substack n\leq N \\ p|n} 1 =\sum_{\substack p\leq N \\ p\text{ prime}} \left\lfloor \frac N p\right\rfloor$$

The last step is because:

$$\sum_{\substack n\leq N \\ p|n} 1 = \left\lfloor \frac N p\right\rfloor$$

The key to changing the order of summation is to write out the set of pairs that you are summing over.
In this case, you are summing over all pairs, $(n,p)$ with the condition $p|n$, $n\leq N$ and $p$ is prime. The original form is to sum over all $n$ and then find the corresponding set of $p$. The "change" is to list all possible $p$ first, namely, the primes $p\leq N$, and then list all the $n\leq N$ which are multiples of $p$.

Edit

You can actually remove the condition $p\leq N$ since it is redundant:

$$\sum_{n\leq N} \sum_{\substack p|n \\ p \text{ prime}} 1= \sum_{p\text{ prime}} \sum_{\substack n\leq N \\ p|n} 1 =\sum_{p\text{ prime}} \left\lfloor \frac N p\right\rfloor$$

This is the same result because $\left\lfloor\frac N p\right\rfloor = 0$ when $p>N$.