神奇的小数部分之和

血狼王

令$\{x\}$代表实数$x$的小数部分。
求证：对一切
$$n\in \mathbb{N},$$
有
$$\sum_{1}^{n} \{\frac{n}{i}\}<\frac{n}{2}.$$

血狼王

这道题看来很难……

isee

不是这题，matrix67.com/blog/archives/5919

matrix67 上的解法看看有没帮助。

abababa

发maven的解答。

最后就是那个$\gamma>\frac{1}{2}$，而且求和都是增的，就能得出来原来的不等式了。

血狼王

回复 4# abababa

多谢大佬

Reinhardt

明显的
\[\sum_{i=1}^n\left[ \frac{n}{i} \right]= \sum_{i=1}^n\tau(n)\]
熟知
\[\sum_{i=1}^n\tau(n)=n\ln n +(2\gamma-1)n+O(n)\]
因此
\[ \sum_{i=1}^n \{\frac{n}{i}\}=(1-\gamma)n-O(\sqrt{n})\]

得证！

ljh25252

厉害，您怎么也来kuing的论坛了

Reinhardt

回复 7# ljh25252


    闲着也是闲着doge

血狼王

回复 6# Reinhardt


    谢谢

hbghlyj

Reinhardt 发表于 2021-9-24 16:23
明显的
\[\sum_{i=1}^n\left[ \frac{n}{i} \right]= \sum_{i=1}^n\tau(n)\]

这里的 $\tau(n)$ 是 $n$ 的因数个数, 在下面记作 $d(n)$.

在AOPS有一个证明 (交换$i,j$求和)
If $d(n)$ is the number of divisors of a positive integer $n$, then
$$d(1)+d(2)+\ldots+d(n)=\lfloor\frac{n}{1}\rfloor+\lfloor\frac{n}{2}\rfloor+\ldots+\lfloor\frac{n}{n}\rfloor$$Proof of the claim:
\begin{align*} d(1)+d(2)+\ldots+d(n)&=\sum_{j=1}^{n}{\sum_{i|j}{1}}\\ &=\sum_{i=1}^{n}{\sum_{\substack{1\le j\le n\\ i|j}}{1}}\\ &=\sum_{i=1}^{n}{\lfloor\frac{n}{i}\rfloor}=\lfloor\frac{n}{1}\rfloor+\lfloor\frac{n}{2}\rfloor+\ldots+\lfloor\frac{n}{n}\rfloor \end{align*}as desired.

hbghlyj

abababa 发表于 2021-8-3 06:56
发maven的解答。

最后就是那个$\gamma>\frac{1}{2}$，而且求和都是增的，就能得出来原来的不等式了。 ...

第一个Riemann sum的$=$应该是$<$吧? 或者加上$\lim$
\begin{aligned}
\lim_{n\to\infty}\frac{1}{n} \sum_{k=1}^n\left\{\frac{n}{k}\right\} & =\int_0^1\left\{\frac{1}{x}\right\} d x \xlongequal{x \rightarrow \frac{1}{x}}\int_1^{\infty} \frac{\{x\}}{x^2} d x=\sum_{k=1}^{\infty} \int_k^{k+1} \frac{x-k}{x^2} d x,[x \in(k, k+1) \Rightarrow\{x\}=x-k] \\
& =\sum_{k=1}^{\infty}\left(\ln \frac{k+1}{k}-\frac{1}{k+1}\right)=\lim _{n \rightarrow \infty}\left(\sum_{k=1}^n \ln \frac{k+1}{k}-\sum_{k=1}^n \frac{1}{k+1}\right) \\
& =\lim _{n \rightarrow \infty}\left(\ln (n+1)-\left[-1+\sum_{k=1}^{n+1} \frac{1}{k}\right]\right) \\
& =1-\gamma
\end{aligned}

hbghlyj

Asymptotic of a sum evaluation as x→∞

ADDED LATER: Everything I originally wrote below was correct. However there is a much better way to look at this that I neglected to mention.

The most important feature of this sum is that it is equal to divisor summatory function $M_\tau$, $$\sum_{n \leq x} \left[\frac{x}{n}\right] = \sum_{n \leq x} \sum_{d \leq x/n} 1 = \sum_{dn \leq x} 1 = \sum_{m \leq x} \sum_{d | m} 1 = \sum_{m \leq x} \tau(m) = M_\tau(x),$$ where $\tau(m) = \sum_{d|m}1$ is the number of divisors of $m$.

Using the hyperbola method, we can easily get the bound $$\sum_{n \leq x} \left[\frac{x}{n}\right] = M_\tau(x) = x \log x + (2\gamma-1)x + O(x^{1/2}).$$

Of course, the divisor summatory function has been most intensively studied and better bounds are available. The best bound to date is by Huxley, who proved $$M_\tau(x) = x \log x + (2\gamma-1)x + O(x^{131/416 + \epsilon}).$$

The smallest $\theta$ for which the error term $O(x^{\theta+\epsilon})$ holds true is known as the Dirichlet divisor problem. Thus we know $\theta \leq 131/416$. But also Hardy and Landau showed that $\theta \geq 1/4$, which tells us that we should abandon our hope of ever having a constant term in our asymptotic expansion; there is no possible constant for which such an asymptotic can be true.

---

ORIGINAL ANSWER: So what you write is not quite correct.

Let $\{x\} = x - [x]$ denote the fractional part of $x$. Then $\{x\}=O(1)$ and $[x]=x+O(1)$. So we have a crude estimate, $$\sum_{n \leq x} \left[\frac{x}{n}\right] = \sum_{n \leq x} \left( \frac{x}{n} - \left\{\frac{x}{n}\right\} \right) = x\sum_{n \leq x} \frac{1}{n} + O\left(\sum_{n \leq x} 1 \right) = x\left(\log x + \gamma + \frac{1}{2x} + O(x^{-2})\right) + O(x) = x\log x + O(x),$$ so we have the asymptotic,

$$\sum_{n \leq x} \left[\frac{x}{n}\right] \sim x \log x.$$

This is the most that you can conclude without a more precise estimate of the sums of the fractional parts $\sum_{n \leq x}\{x/n\}$.

To attempt to get a more precise estimate, one interesting question to ask is what is $$\lim_{x \rightarrow \infty} \frac{1}{x} \sum_{n \leq x} \left\{\frac{x}{n}\right\} = \; ?$$ If we were to assume that the fractional parts were uniformly distributed, we would conclude that that the limit would be $1/2$. But that would be wrong! Somewhat surprisingly, that sum is in fact a Riemann sum, and can be written as an integral, $$\lim_{x \rightarrow \infty} \frac{1}{x} \sum_{n \leq x} \left\{\frac{x}{n}\right\} = \int_0^1 \left\{\frac{1}{t}\right\} \, dt.$$ The integrand is piecewise continuous, and we can break the integral into pieces, $$\int_0^1 \left\{\frac{1}{t}\right\} \, dt = \sum_{k=1}^\infty \int_{1/(k+1)}^{1/k} \left(\frac{1}{t} - k\right) \, dt = \sum_{k=1}^\infty \left( \log(k+1) - \log(k) - \frac{1}{k+1}\right) = \lim_{K \rightarrow \infty} \left( \log(K+1) - \sum_{k=1}^K \frac{1}{k+1} \right) = 1 - \gamma.$$ We conclude that $$\sum_{n \leq x} \left\{\frac{x}{n}\right\} \sim (1 - \gamma)x.$$ We can use this to refine our earlier estimate, $$\sum_{n \leq x} \left[\frac{x}{n}\right] = \sum_{n \leq x} \frac{x}{n} - \sum_{n \leq x} \left\{\frac{x}{n}\right\} = x\left(\log x + \gamma + \frac{1}{2x} + O(x^{-2})\right) - \left(1-\gamma+o(1)\right)(x) \\ = x\log x + (2\gamma -1)x + o(x).$$ Thus, we now have a more precise asymptotic,

$$\sum_{n \leq x} \left[\frac{x}{n}\right] \sim x\log x + (2\gamma -1)x.$$

Note we haven't justified a particular constant term in our asymptotic expansion.