取整函数

<image>

<image>

在数学和计算机科学中，取整函数是一类将实数映射到相近的整数的函数。

常用的取整函数有两个，分别是下取整函数（floor function）和上取整函数（ceiling function）。

下取整函数即为取底符号，在数学中一般记作$[ x ]$或者$\lfloor x \rfloor$或者$E(x)$，在计算机科学中一般记作floor(x)，表示不超过x的整数中最大的一个。

$$[ x ]=\max\, \{n\in\mathbb{Z}\mid n\le x\}.$$

举例来说，$[ 3.633 ] = 3$，$[ 56 ] = 56$，$[ -2 ] = -2$，$[ -2.263 ] = -3$。对于非负的实数，其下取整函数的值一般叫做它的整数部分或取整部分。而$x -[ x]$叫做x的小数部分。每个分数都可以表示成其整数部分与一个真分数的和，而实数的整数部分和小数部分是与此概念相应的拓延。

下取整函数的符号用方括号表示（$[x]$），称作高斯符号，首次出现是在卡尔·弗里德里希·高斯的数学著作《算术研究》。

上取整函数即为取顶符号在数学中一般记作$\lceil x \rceil$，在计算机科学中一般记作ceil(x)，表示不小于x的整数中最小的一个。

$$\lceil x \rceil=\min\{n\in\mathbb{Z}\mid x\le n\}.$$

举例来说，$\lceil 3.633 \rceil = 4$，$\lceil 56 \rceil = 56$，$\lceil -2 \rceil = -2$，$\lceil -2.263 \rceil = -2$。

计算机中的上取整函数和下取整函数的命名来自于英文的ceiling（天花板）和floor（地板），1962年由肯尼斯·艾佛森于《A Programming Language》引入。

## 性质

对于高斯符号，有如下性质。

- $[ x] \le x < [ x ] + 1$; 当且仅当 $x$ 为整数时取等号。
- 设 $x$ 和 $n$ 为正整数，则：
- $$\left[ \frac{n}{x} \right] \geq \frac{n}{x} - \frac{x-1}{x}$$
- 当 $n$ 为正整数时，有：
- $\left[ \frac{x}{n} \right] = \frac{x-x\bmod n}{n},$ 其中 $x \bmod n$ 表示 $x$ 除以 $n$ 的余数。
- 对任意的整数 $k$ 和任意实数 $x$。
- $$[ {k+x} ] = k + [ x].$$
- 一般的数值修约规则可以表述为将 $x$ 映射到 $\left[ x + 0.5 \right]$。
- 高斯符号不是连续函数，但是上半连续的。作为一个分段的常数函数，在其导数有定义的地方，高斯符号导数为零。
- 设 $x$ 为一个实数，$n$ 为整数，则由定义，$n \leq x$ 当且仅当 $n \leq \left[ x\right]$。
- 当 $x$ 是正数时，有：
- $$\left[ 2 x \right] - 2 \left[ x \right] \leqslant 1$$
- 用高斯符号可以写出若干个素数公式，但没有什么实际价值，见#质数公式。
- 对于非整数的 $x$，高斯符号有如下的傅里叶级数展开：
- $$[ x] = x - \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^\infty \frac{\sin(2 \pi k x)}{k}.$$
- 根据Beatty定理，每个正无理数都可以通过高斯符号制造出一个整数集的分划。
- 最后，对于每个正整数 $k$，其在 p 进制下的表示有 $[ \log_{p}(k) ] + 1$ 个数位。

### 函数间之关系

由上下取整函数的定义，可见

$$\lfloor x \rfloor \le \lceil x \rceil,$$

等号当且仅当$x$为整数，即

$$\lceil x \rceil - \lfloor x \rfloor = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}$$

实际上，上取整与下取整函数作用于整数$n$，效果等同恒等函数：

$$\lfloor n \rfloor = \lceil n \rceil = n.$$

自变量加负号，相当于将上取整与下取整互换，外面再加负号，即：

$$\begin{align} \lfloor x \rfloor +\lceil -x \rceil &= 0, \\ -\lfloor x \rfloor &= \lceil -x \rceil, \\ -\lceil x \rceil &= \lfloor -x \rfloor. \end{align}$$

且：

$$\lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ -1,&\text{ 若 }\ x\not\in \mathbb{Z}, \end{cases}$$

$$\lceil x \rceil + \lceil -x \rceil = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}$$

至于小数部分$\{x \} = x - \lfloor x \rfloor$，自变量取相反数会使小数部分变成关于1的“补数”：

$$\{ x \} + \{ -x \} = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}$$

上取整、下取整、小数部分皆为幂等函数，即函数迭代两次的结果等于自身：

$$\begin{align} \Big\lfloor \lfloor x \rfloor \Big\rfloor &= \lfloor x \rfloor, \\ \Big\lceil \lceil x \rceil \Big\rceil &= \lceil x \rceil, \\ \Big\{ \{ x \} \Big\} &= \{ x \}. \end{align}$$

而多个上取整与下取整依次迭代的效果，相当于最内层一个：

$$\begin{align} \Big\lfloor \lceil x \rceil \Big\rfloor &= \lceil x \rceil, \\ \Big\lceil \lfloor x \rfloor \Big\rceil &= \lfloor x \rfloor, \end{align}$$

因为外层取整函数实际只作用在整数上，不带来变化。

### 商

若$m$和$n$为正整数，且$n \neq 0$，则

$$0 \le \left \{\frac{m}{n} \right\} \le 1-\frac{1}{|n|}.$$

若$n$为正整数，则

$$\left\lfloor\frac{x+m}{n}\right\rfloor = \left\lfloor\frac{\lfloor x\rfloor +m}{n}\right\rfloor,$$

$$\left\lceil\frac{x+m}{n}\right\rceil = \left\lceil\frac{\lceil x\rceil +m}{n}\right\rceil.$$

若$m$为正数，则

$$n=\left\lceil\frac{n}{m}\right\rceil + \left\lceil\frac{n-1}{m}\right\rceil +\dots+\left\lceil\frac{n-m+1}{m}\right\rceil,$$

$$n=\left\lfloor\frac{n}{m}\right\rfloor + \left\lfloor\frac{n+1}{m}\right\rfloor +\dots+\left\lfloor\frac{n+m-1}{m}\right\rfloor.$$

代$m = 2$，上式推出：

$$n= \left\lfloor \frac{n}{2}\right \rfloor + \left\lceil\frac{n}{2}\right \rceil.$$

更一般地，对正整数$m$，有埃尔米特恒等式：

$$\lceil mx \rceil =\left\lceil x\right\rceil + \left\lceil x-\frac{1}{m}\right\rceil +\dots+\left\lceil x-\frac{m-1}{m}\right\rceil,$$

$$\lfloor mx \rfloor=\left\lfloor x\right\rfloor + \left\lfloor x+\frac{1}{m}\right\rfloor +\dots+\left\lfloor x+\frac{m-1}{m}\right\rfloor.$$

对于正整数$m$，以下两式可将上下取整函数互相转化：

$$\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1,$$

$$\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil = \left\lceil \frac{n + 1}{m} \right\rceil - 1.$$

对任意正整数$m$和$n$，有：

$$\sum_{k = 1}^{n - 1} \left\lfloor \frac{k m}{n} \right\rfloor = \frac{(m - 1)(n - 1)+\gcd(m,n)-1}2,$$

作为特例，当$m$和$n$互质时，上式简化为

$$\sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor = \frac{1}{2}(m - 1)(n - 1).$$

此等式可以几何方式证明。又由于右式关于$m$、$n$对称，可得

$$\left\lfloor \frac{m}{n} \right \rfloor + \left\lfloor \frac{2m}{n} \right \rfloor + \dots + \left\lfloor \frac{(n-1)m}{n} \right \rfloor = \left\lfloor \frac{n}{m} \right \rfloor + \left\lfloor \frac{2n}{m} \right \rfloor + \dots + \left\lfloor \frac{(m-1)n}{m} \right \rfloor.$$

更一般地，对正整数$m, n$，有

$$\begin{align} &\left\lfloor \frac{x}{n} \right \rfloor + \left\lfloor \frac{m+x}{n} \right \rfloor + \left\lfloor \frac{2m+x}{n} \right \rfloor + \dots + \left\lfloor \frac{(n-1)m+x}{n} \right \rfloor\\= &\left\lfloor \frac{x}{m} \right \rfloor + \left\lfloor \frac{n+x}{m} \right \rfloor + \left\lfloor \frac{2n+x}{m} \right \rfloor + \cdots + \left\lfloor \frac{(m-1)n+x}{m} \right \rfloor. \end{align}$$

上式算是一种“互反律”（reciprocity law），与#二次互反律有关。

## 应用

### 二次互反律

高斯给出二次互反律的第三个证明，经艾森斯坦修改后，有以下两个主要步骤。

设$p$、$q$为互异奇质数，又设

$m = \frac{p - 1}{2},$ $n = \frac{q - 1}{2}.$

首先，利用高斯引理，证明勒让德符号可表示为和式：

$$\left(\frac{q}{p}\right) = (-1)^{\left\lfloor\frac{q}{p}\right\rfloor +\left\lfloor\frac{2q}{p}\right\rfloor +\dots +\left\lfloor\frac{mq}{p}\right\rfloor },$$

同样

$$\left(\frac{p}{q}\right) = (-1)^{\left\lfloor\frac{p}{q}\right\rfloor +\left\lfloor\frac{2p}{q}\right\rfloor +\dots +\left\lfloor\frac{np}{q}\right\rfloor }.$$

其后，采用几何论证，证明

$$\left\lfloor\frac{q}{p}\right\rfloor +\left\lfloor\frac{2q}{p}\right\rfloor +\dots +\left\lfloor\frac{mq}{p}\right\rfloor +\left\lfloor\frac{p}{q}\right\rfloor +\left\lfloor\frac{2p}{q}\right\rfloor +\dots +\left\lfloor\frac{np}{q}\right\rfloor = mn.$$

总结上述两步，得

$$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{mn}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.$$

此即二次互反律。一些小整数模奇质数$p$的二次特征标，可以高斯符号表示，如：

$$\left(\frac{2}{p}\right) = (-1)^{\left\lfloor\frac{p+1}{4}\right\rfloor},$$

$$\left(\frac{3}{p}\right) = (-1)^{\left\lfloor\frac{p+1}{6}\right\rfloor}.$$

### 质数公式

下取整函数出现于若干刻画质数的公式之中。举例，因为$\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor$在$m$整除$n$时等于$1$，否则为$0$，所以正整数$n$为质数当且仅当

$\infty$

$n$

$n > 1$

$\sum_{m=1}^{\lfloor \sqrt n \rfloor}\left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right) = 1.$

$$\sum_{m=1}^{\infty}\left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right) = 2.$$

除表示质数的条件外，还可以写出公式使其取值为质数。例如，记第$n$个质数为$p_n$，任选一个整数$r > 1$，然后定义实数$\alpha$为

$$\alpha = \sum_{m=1}^\infty p_m r^{-m^2}.$$

则只用取整、幂、四则运算可以写出质数公式：

$$p_n = \left\lfloor r^{n^2}\alpha \right\rfloor - r^{2n-1}\left\lfloor r^{(n-1)^2}\alpha\right\rfloor.$$

类似还有米尔斯常数$\theta = 1.3064\ldots$，使

$$\left\lfloor \theta^3 \right\rfloor, \left\lfloor \theta^9 \right\rfloor, \left\lfloor \theta^{27} \right\rfloor, \dots$$

皆为质数。

若不迭代三次方函数，改为迭代以$2$为㡳的指数函数，亦有$\omega = 1.9287800\ldots$使

$$\left\lfloor 2^\omega\right\rfloor, \left\lfloor 2^{2^\omega} \right\rfloor, \left\lfloor 2^{2^{2^\omega}} \right\rfloor, \dots$$

皆为质数。

以质数计算函数$\pi(x)$表示小于或等于$x$的质数个数。由威尔逊定理，可知

$$\pi(n) = \sum_{j=2}^n\left\lfloor\frac{(j-1)!+1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor\right\rfloor.$$

又或者，当$n \ge 2$时：

$$\pi(n) = \sum_{j=2}^n \left\lfloor \frac{1}{\sum_{k=2}^j\left\lfloor\left\lfloor\frac{j}{k}\right\rfloor\frac{k}{j}\right\rfloor}\right\rfloor.$$

本小节的公式未有任何实际用途。

$\alpha$

## 其它等式

- 对于所有实数x，有：

$$\left\lfloor \frac{x}{2} \right\rfloor = \frac{1}{4} ((-1)^{\lfloor x \rfloor}-1 + 2 \lfloor x \rfloor )$$

$$\left\lfloor \frac{x}{3} \right\rfloor = \frac{1}{3} (\frac{2}{\sqrt{3}} \sin(\frac{2\pi}{3}\lfloor x \rfloor + \frac{\pi}{3}) - 1 + \lfloor x \rfloor )$$