# Change of order of summation.

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 | N} \pi(n)$$ any further?

where obviously $\pi(n)$ is prime numbers counting function.

Thanks in advance.

-
changing the order of summation is the WORST. don't feel like an idiot! – user29743 Jul 5 '12 at 15:37
(by WORST, i mean, it is the computational operation that makes me the most likely to get confused, not the least effective one!) – user29743 Jul 5 '12 at 15:38
What happened to $n\leq N$? You seem to have changed it to $n|N$. – Thomas Andrews Jul 5 '12 at 15:45
I don't see where you changed the order of summation.. – Cocopuffs Jul 5 '12 at 15:45

## 1 Answer

It looks like your answer is wrong.

The correct change is:

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

The last step is because:

$$\sum_{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_{p|n}_{p \text{ prime}} 1= \sum_{p\text{ prime}} \sum_{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$.

-