2/16 笔记

《具体数学》第四章笔记

  • 关于二重和式的交换
    $$
    \sum_{m \mid n}{\sum_{k | m}}{a_{k,m}} = \sum_{k \mid n}{\sum_{l | (n / k)}{a_{k,kl}}}
    $$

简单证明如下

$$
\begin{aligned}
\sum_{m\mid n}{\sum_{k\mid m}}{a_{k,m}} &= \sum_{i,j}{\sum_{m,n > 0}}{a_{k,m}[n = mi][m = kj]} &= \sum_{i}{\sum_{k,j > 0}a_{k,kj}[n=kij]} \\
\sum_{k \mid n}{\sum_{l \mid (n / k)}}{a_{k,kl}} &= \sum_{i}{\sum_{j}{a_{k,kl}}[n = ik][\dfrac{n}{k} = jl]} &= \sum_{i}{\sum_{j}{a_{k,kl}}[n = kjl]}
\end{aligned}
$$
所以 $LHS = RHS$

  • 欧几里得数

由经典的“素数有无穷多个”的证明,我们可以引出欧几里得数。定义欧几里得数 $e_{n} = \prod_{i = 1}^{n-1}{e_{i}} + 1, e_{1} = 2$ ,则不难看出,相邻两项 $e_{n}\bmod e_{n-1} = 1$ ,因此相邻两项互素。也可以对定义做一些改写得到 $e_{n} = e_{n-1}^2 – e_{n-1} + 1$. 这样 $e_{n}$ 的十进制位数为 $e_{n-1}$ 的两倍左右。

  • 阶乘的因子

记 $f_{p}(n!)$ 代表数字 $n!$ 的素因子分解中 $p$ 的幂。不难看出,
$$
f_{p}(n!) = \sum_{i=1}{\bigg \lfloor \dfrac{n}{p^i} \bigg \rfloor}
$$
考虑 $p = 2$ 的特殊情形。注意到 $\bigg \lfloor \dfrac{n}{2^i} \bigg \rfloor = \bigg \lfloor \dfrac{\big \lfloor\dfrac{n}{2^{i-1}}\big \rfloor}{2} \bigg \rfloor$

这意味着 $f_{2}(n!)$ 应该与 $n$ 的二进制表示有关。只需每次右移一位,然后把答案累加即可。

在考虑这个和式的上界,由于 $\bigg \lfloor \dfrac{n}{p^i} \bigg \rfloor \leq \dfrac{n}{p^i}$,因此
$$
\begin{aligned}
f_{p}{(n!)} &< \sum{\dfrac{n}{p^i}} \\
&= \dfrac{n}{p}(\dfrac{p}{p-1}) \\
&= \dfrac{n}{p – 1}
\end{aligned}
$$

  • 中位分数
    (待续)

发表评论