Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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$.


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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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