Consider the well known identity from elementary number theory:

$$\sum_{k=1}^n \tau(k)=\sum_{d=1}^n \left\lfloor \frac{n}{d} \right\rfloor,$$ where of course the asymptotic expression for both sides is $n \log n + (2\gamma-1) n + O(\sqrt{n}).$

Some experimentation with Maple seems to show that if $v:=\frac{n}{\log n},$ then $$ F(v):=\lim_{n\rightarrow \infty} \frac{\sum_{d=1}^{\lfloor v\rfloor} \left\lfloor \frac{n}{d} \right\rfloor }{\sum_{d=1}^n \left\lfloor \frac{n}{d} \right\rfloor },\quad (1) $$ is increasing towards $1$ from below.

Is it possible to prove what the limit in (1) is, if $v=c\frac{n}{\log n},$ for some $c \in (0,1)$?


migrated from mathoverflow.net Jan 25 '17 at 16:17

This question came from our site for professional mathematicians.

  • 1
    $\begingroup$ The difference between the top and the bottom should not be far from n(log((log n)/c)-1). Gerhard "Is This Estimate Close Enough?" Paseman, 2017.01.24. $\endgroup$ – Gerhard Paseman Jan 25 '17 at 6:36
  • $\begingroup$ As @GerhardPaseman says, this seems straightforward: $1-F(\nu)$ is the ratio of the sum from $\nu$ to $n$ divided by the sum from $1$ to $n$. You already have an estimate for the sum from $1$ to $n$, so you just need to prove the sum from $\nu$ to $n$ is of smaller order (which you can do by estimating the terms in the sum). $\endgroup$ – anthonyquas Jan 25 '17 at 6:53
  • $\begingroup$ Thanks, I will have a go at it and try to formulate an answer. $\endgroup$ – kodlu Jan 25 '17 at 7:11

The limit can be estimated via (recalling $v=\frac{c n}{\log n}$): $$ 1-F(v)=\frac{\sum_{d=\lfloor v \rfloor +1}^n \lfloor \frac{n}{d} \rfloor} {\sum_{d=1}^n \lfloor \frac{n}{d} \rfloor} \geq \frac{(n-\frac{cn}{\log n})\log n}{n \log n + (2\gamma-1)n+O(\sqrt{n})} \sim 1-c(\log n)^{-1} $$ by upper bounding the top of the numerator by number of terms times the largest term of the sum.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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