Return to Revisions

The conjecture is true. For $t\in[0,1]$, let $N(t)$ be the number of $k\in\{1,2,\dotsc,n\}$ satisfying $\{n/k\}\leq t$. On the one hand, $$\sum_{k=1}^n f\left(\frac{n}{k}\right)=\int_{1/2}^1 N(t)\,dt-\int_0^{1/2}N(t)\,dt=\int_0^{1/2}N(t+1/2)-N(t)\,dt.$$ On the other hand, for any positive integer $M$, $$N(t)=\sum_{m=1}^\infty\left(\biggl\lfloor\frac{n}{m}\biggr\rfloor-\biggl\lfloor\frac{n}{m+t}\biggr\rfloor\right)=\sum_{m=1}^M\left(\frac{n}{m}-\frac{n}{m+t}\right)+O\left(M+\frac{n}{M}\right).$$ It follows that \begin{align*} \sum_{k=1}^n f\left(\frac{n}{k}\right) &=\sum_{m=1}^M\int_0^{1/2}\left(\frac{n}{m+t}-\frac{n}{m+t+1/2}\right)\,dt+O\left(M+\frac{n}{M}\right)\\ &=n\log\prod_{m=1}^M\frac{(2m+1)^2}{(2m)(2m+2)}+O\left(M+\frac{n}{M}\right). \end{align*} By Wallis's product, $$\prod_{m=1}^\infty\frac{(2m+1)^2}{(2m)(2m+2)}=\frac{4}{\pi},$$ hence also $$\prod_{m=1}^M\frac{(2m+1)^2}{(2m)(2m+2)}=\frac{4}{\pi}\prod_{m=M+1}^\infty\frac{(2m)(2m+2)}{(2m+1)^2}=\frac{4}{\pi}\left(1+O\left(\frac{1}{M}\right)\right).$$ Taking the logarithm of both sides, and going back to our sum, $$\sum_{k=1}^n f\left(\frac{n}{k}\right)=n\log\left(\frac{4}{\pi}\right)+O\left(M+\frac{n}{M}\right).$$ Finally, we choose $M=\lfloor\sqrt{n}\rfloor$ to conclude that $$\sum_{k=1}^n f\left(\frac{n}{k}\right)=n\log\left(\frac{4}{\pi}\right)+O\left(\sqrt{n}\right).$$