0
$\begingroup$

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

$\endgroup$
3
  • 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
    Commented Jan 25, 2017 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
    Commented Jan 25, 2017 at 6:53
  • $\begingroup$ Thanks, I will have a go at it and try to formulate an answer. $\endgroup$
    – kodlu
    Commented Jan 25, 2017 at 7:11

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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