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

$$\sum_{i,j=1}^{\infty}\left[\frac{x}{p_ip_j}\right]=x\sum_{p_ip_j\leq x}\frac{1}{p_ip_j}+O(x),p_i< p_j$$ where $p_i$ is the $i$th prime, and "[ ]" represents the largest integer not exceeding...

I don't know how to deal with it. Could you give me a proof?

share|cite|improve this question
This was a fun question to answer. I liked it =) – Patrick Da Silva Dec 7 '11 at 4:43
up vote 6 down vote accepted

The sum on the left is $$ \sum_{i,j=1}^{\infty} \left[ \frac x{p_i p_j} \right] = \sum_{p_i p_j \le x} \left[ \frac{x}{p_i p_j} \right] $$ because if $p_i p_j > x$ then the integer part is just $0$, hence you don't need to sum over infinitely many terms. It remains to see that there is $O(x)$ terms in that sum, since $$ z = [z] + \{z\} \qquad \text{ with } \qquad \{z\} \le 1. $$ so that you can look at the sum on the left as the sum on your right + the remainders, which you will only need to "count" how many of them appear, since all the terms you will sum will be less than $1$. Hence showing that there is at most $O(x)$ terms in that sum shows that you can bound the remainder's sum by $O(x) \times 1 = O(x)$.

The number of terms in that sum is $$\begin{align*} \# \left\{ (p_i,p_j) \, | \, p_i p_j \le x, p_i < p_j \right\} &\le \, \# \left \{ n \, | \, n \text{ is composite }, n \le x \right \} \\ &= x - \pi(x) \\ &\sim x - \frac {x}{\log x} \\ &= O(x). \end{align*}$$ (A rough bound though would just be $x$ and it would still be $O(x)$, I just thought I'd do a little better.)

(ADDED : Aleks was wondering why my inequality held, so I'll add the proof here. Call the set with the prime couples $A$ and the set with the composites $B$. The application which takes a couple $(p_i, p_j)$ with $p_i < p_j$ to their product $p_i p_j = n$ is injective, for if $p_i^1 p_j^1 = n_1 = n_2 = p_i^2 p_j^2$, since $p_i^k < p_j^k$ we must have $p_i^1 = p_i^2$ and $p_j^1 = p_j^2$. Since this application is injective, $\# A \le \# B$. )

This gives you $$\begin{align*} \sum_{i,j=1}^{\infty} \left[ \frac{x}{p_i p_j} \right] &= \sum_{p_i p_j \le x} \left[ \frac x{p_i p_j} \right]\\ &= \sum_{p_i p_j \le x} \left( \frac x{p_i p_j} - \left\{ \frac{x}{p_ip_j} \right\} \right)\\ &= x \left( \sum_{p_i p_j \le x} \frac 1{p_i p_j} \right) - \sum_{p_i p_j \le x} \left\{ \frac{x}{p_ip_j} \right\} \end{align*}$$ and since the last sum contains $O(x)$ terms less than $1$, it is $O(x)$.

Hope that helps,

share|cite|improve this answer
Patrick, the OP has the extra condition that $p_i < p_j$. – Aleks Vlasev Dec 7 '11 at 3:23
I think I'm finally done editing. Heh – Patrick Da Silva Dec 7 '11 at 3:33
Oh, thanks for the remark Aleks. Looks like I'm not done editing.. – Patrick Da Silva Dec 7 '11 at 3:34
Your formula is not right ; it goes more like $$ \sum_{i=1}^{\pi(x)} \pi(x/p_i) $$ which is strictly less what you're looking for. You can't just sum it like you did ; $\pi$ is clearly not a linear function in $p_i$. – Patrick Da Silva Dec 7 '11 at 19:01
@PatrickDaSilva: Ok ya, I forgot. It is cool though: $$\sum_{pq\leq x}\frac{1}{pq}=\left(\log\log x\right)^{2}+B_{1}^{2}-\frac{\pi^{2}}{6}+O\left(\frac{\log \log x}{\log x}\right),$$ where $B_1$ is Mertens Constant. – Eric Naslund Dec 9 '11 at 6:08

Since $\pi_2(x):=\#\{n \leq x:\omega(n)=2 \}\ll \frac{x}{(\log x)^2}(\log \log x)^2$, the error term is $\frac{x}{(\log x)^2}(\log \log x)^2=o(x).$ $\omega(n)$ denotes the number of primes dividing $n$.

share|cite|improve this answer
Why does $n$ still appear in the error term? Also note that $x$ might be a real number, not an integer. – Patrick Da Silva Dec 7 '11 at 19:03
Good question but. The dot is usually used to separate two different statements. – Captain Darling Dec 8 '11 at 13:01
XD Haha. Nice. I thought it was just a weird way of multiplying stuff, sorry for that one. – Patrick Da Silva Dec 8 '11 at 16:38
This is not completely correct, rather $\pi_2(x)\sim \frac{x}{\log x}\log\log x.$ – Eric Naslund Dec 9 '11 at 5:36

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.