I would like to ask if there is a good upper bound on the difference $$D_2(n)=\sum_{n^{1/3}<p,q\leq n^{1/2}} \left(\frac{n}{pq}-\left\lfloor \frac{n}{pq}\right\rfloor\right)\quad (1) $$where $p$ and $q$ range over primes in the given interval. I believe that the ratio $$R_2(n)=\frac{\sum_{n^{1/3}<p,q\leq n^{1/2}} \left\lfloor \frac{n}{pq}\right\rfloor}{\sum_{n^{1/3}<p,q\leq n^{1/2}} \frac{n}{pq} }\quad (2)$$ approaches 1, as $n\rightarrow \infty$ from below.

Question 1: Is the claimed limit for (2) correct? How would it be proved rigorously?

Question 2: Is there a tight upper bound on $D_2(n)$ as $n$ goes to infinity?

More generally, define

$$D_k(n)=\sum_{n^{1/(k+1)}<p_1,\ldots,p_k\leq n^{1/k}} \left(\frac{n}{p_1 p_2 \cdots p_k}-\left\lfloor \frac{n}{p_1 p_2 \cdots p_k}\right\rfloor\right)$$ where the $p_i$ range over primes in the interval given, and define $R_k(n)$ analogously.

Can Questions 1 and 2 be answered for these quantities? Note that I am intersted in both the case of $k$ fixed, as well as $k$ slowly growing, but satisfying $k\leq c \lfloor \log \log n \rfloor,$ with $c<2$ a constant. My goal is to approximate the sum with the floor functions by means of the sum without the floor functions.

  • 1
    $\begingroup$ You should be able to get something straightforward by comparing your D_2 to the special sum of n/pq. In particular, all the D_2 terms are at most 1 while most of the terms in the special sum range from 2 up to n^1/3, so you should be able to show the ratio goes to 0, which would answer question 1 (note this avoids some of the issues in wanting a good estimate on $\pi(n^{1/2})$. For question 2, a tight upper bound on D_2 would need to be as good as a similar bound on $\pi(n^{1/2})$. I think these remarks can extend to k > 2. Gerhard "Helps To Use Error-free Arguments" Paseman, 2016.03.15. $\endgroup$ Mar 16, 2016 at 1:53
  • 1
    $\begingroup$ Hey so the denominator is order n (it's n times (\sum 1/p)^2 ~ n (loglog(n^{1/2}) - loglog(n^{1/3})) = const*n)), and the error, D_2, is bounded by the number of terms, which is order n/(log n)^2, so you're ok I think. $\endgroup$
    – alpoge
    Mar 16, 2016 at 14:56
  • $\begingroup$ @GerhardPaseman thanks. Very useful. $\endgroup$
    – kodlu
    Mar 16, 2016 at 21:24
  • $\begingroup$ @alpoge thank you. I will try to write a full answer. $\endgroup$
    – kodlu
    Mar 16, 2016 at 21:25
  • $\begingroup$ @GerhardPaseman, do you see any problems with my proposed answer? Thanks. $\endgroup$
    – kodlu
    Mar 23, 2016 at 7:06

1 Answer 1


Based on @GerhardPaseman and @alpoge's remarks I have written this answer, for $k=2.$ Consider $$ D_2(n)=\sum_{n^{1/3}<p,q\leq n^{1/2}} \left(\frac{n}{pq}-\left\lfloor \frac{n}{pq}\right\rfloor\right)\quad (1) $$ where $p,q$ are primes, and note that each term in (1) is positive, and in $[0,1),$ which gives $$ D_2(n)<\#\{p \in (n^{1/3},n^{1/2}]: p~~a~~prime~\}^2=[\pi(n^{1/2})-\pi(n^{1/3})]^2=$$ $$ \approx \left[\frac{2n^{1/2}}{\log n}-\frac{3n^{1/3}}{\log n}\right]^2\ll \frac{n}{\log^2 n}.$$ Now consider the approximating sum $$ S_2'(n)=\sum_{n^{1/3}<p,q\leq n^{1/2}} \frac{n}{pq}=\left[\sum_{n^{1/3}<p\leq n^{1/2}}\frac{\sqrt{n}}{p}\right]^2=n\left[\sum_{n^{1/3}<p\leq n^{1/2}}p^{-1}\right]^2\asymp $$ $$ \asymp n [\log\log(n^{1/2})-\log\log(n^{1/3})]^2=\log^2(3/2) n =c~ n,\quad(2) $$ with $c \in (0,1).$ From (1), the sum I am interested in satisfies $$ S_2(n)=\sum_{n^{1/3}<p,q\leq n^{1/2}} \left\lfloor \frac{n}{pq}\right\rfloor> c~n -\frac{n}{\log^2 n} \gg c~n$$ for $n$ large enough.

For $k$ larger and fixed, one can argue essentially the same way, and the implied constant $c$ in (2) becomes $\log^2((k+1)/k)$ so increasingly smaller.

The open question is, what can be done, if anything, to lower bound $$ S_k(n)=\sum_{n^{1/(k+1)}<p_1,\ldots,p_k\leq n^{1/k}} \left\lfloor \frac{n}{p_1 p_2 \cdots p_k}\right\rfloor $$ for $k=\alpha \log\log n,$ and $0<\alpha<2.$

  • $\begingroup$ For increased enlightenment, you might compare this with $\sum_{d\in D} (n/d - \lfloor n/d \rfloor)$ for various subsets $D \subseteq [1,\ldots,n]$. For the biggest such $D$, Euler gives a constant upper and lower bound, and you are taking multiples of pieces of that constant. As long as the multiples don't outgrow the (inverse of the) size of the pieces, you should be OK. Gerhard "Likes The Use Of Mertens" Paseman, 2016.03.23. $\endgroup$ Mar 23, 2016 at 17:12
  • $\begingroup$ Actually, I misspoke. Euler gives a constant bound for a different sum. However, I think that you can relate your sum to his and possibly get more refined estimates. (I am talking log n - the nth Harmonic number.) Gerhard "Sorry For Any Confusion Caused" Paseman, 2016.03.23. $\endgroup$ Mar 23, 2016 at 17:32
  • $\begingroup$ @GerhardPaseman, thanks, I will try to do this. $\endgroup$
    – kodlu
    Mar 23, 2016 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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