取整函數

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