$$\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?

  • $\begingroup$ This was a fun question to answer. I liked it =) $\endgroup$ Dec 7, 2011 at 4:43

2 Answers 2


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,

  • $\begingroup$ Patrick, the OP has the extra condition that $p_i < p_j$. $\endgroup$ Dec 7, 2011 at 3:23
  • $\begingroup$ I think I'm finally done editing. Heh $\endgroup$ Dec 7, 2011 at 3:33
  • $\begingroup$ Oh, thanks for the remark Aleks. Looks like I'm not done editing.. $\endgroup$ Dec 7, 2011 at 3:34
  • 2
    $\begingroup$ 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$. $\endgroup$ Dec 7, 2011 at 19:01
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 9, 2011 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$.

  • $\begingroup$ Why does $n$ still appear in the error term? Also note that $x$ might be a real number, not an integer. $\endgroup$ Dec 7, 2011 at 19:03
  • $\begingroup$ Good question but. The dot is usually used to separate two different statements. $\endgroup$
    – Mr. No
    Dec 8, 2011 at 13:01
  • $\begingroup$ XD Haha. Nice. I thought it was just a weird way of multiplying stuff, sorry for that one. $\endgroup$ Dec 8, 2011 at 16:38
  • $\begingroup$ This is not completely correct, rather $\pi_2(x)\sim \frac{x}{\log x}\log\log x.$ $\endgroup$ Dec 9, 2011 at 5:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .