向上取整函數

在數學和電腦科學中，**取整函數**是一類將實數對映到相近的整數的函數。

常用的取整函數有兩個，分別是**下取整函數**（英語：floor function）和**上取整函數**（ceiling function）。

**下取整函數**即為**取底符號**，在數學中一般記作 $[x]$ 或者 $\lfloor x\rfloor $ 或者 $E(x)$ ，在電腦科學中一般記作 floor (_x_)，表示不超過 _x_ 的整數中最大的一個。

　
: $[x]=\max \,\{n\in \mathbb {Z} \mid n\leq 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\leq 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]\leq x<[x]+1$ 若且唯若 _x_ 為整數時取等號。
* 設 x 和 n 為正實數，則：

　
: $\left[{\frac {n}{x}}\right]\geq {\frac {n}{x}}-{\frac {x-1}{x}}$
* 當 _n_ 為正整數時，有：

　
: $\left\lbrack {\frac {x}{n}}\right\rbrack ={\frac {x-x{\bmod {n}}}{n}},$ 其中 $x{\bmod {n}}$ 表示 $x$ 除以 $n$ 的餘數。
* 對任意的整數 _k_ 和任意實數 _x_，

　
: $[{k+x}]=k+[x].$
* 一般的數值修約規則可以表述為將 _x_ 對映到 floor (_x_ + 0.5)；
* 高斯符號不是連續函數，但是上半連續的。作為一個分段的常數函數，在其導數有定義的地方，高斯符號導數為零。
* 設 _x_ 為一個實數，_n_ 為整數，則由定義，_n_ ≤ _x_ 若且唯若 _n_ ≤ floor(_x_)。
* 當 _x_ 是正數時，有：

　
: $\left\lbrack 2x\right\rbrack -2\left\lbrack x\right\rbrack \leqslant 1$
* 用高斯符號可以寫出若干個質數公式，但沒有什麼實際價值，見 § 質數公式。
* 對於非整數的 _x_，高斯符號有如下的傅立葉級數展開：

　
: $[x]=x-{\frac {1}{2}}+{\frac {1}{\pi }}\sum _{k=1}^{\infty }{\frac {\sin(2\pi kx)}{k}}.$
* 根據 Beatty 定理，每個正無理數都可以通過高斯符號製造出一個整數集的分劃。
* 最後，對於每個正整數 _k_，其在 p 進位下的表示有 $[\log _{p}(k)]+1$ 個數位。

### 函數間之關係

由上下取整函數的定義，可見

　
: $\lfloor x\rfloor \leq \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{aligned}\lfloor x\rfloor +\lceil -x\rceil &=0,\\-\lfloor x\rfloor &=\lceil -x\rceil ,\\-\lceil x\rceil &=\lfloor -x\rfloor .\end{aligned}}$

且：

　
: $\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{aligned}{\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{aligned}}$

而多個上取整與下取整依次疊代的效果，相當於最內層一個：

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

因為外層取整函數實際衹作用在整數上，不帶來變化。

### 商

若 $m$ 和 $n$ 為正整數，且 $n\neq 0$ ，則

　
: $0\leq \left\{{\frac {m}{n}}\right\}\leq 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 {km}{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{aligned}&\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{aligned}}$

上式算是一種「互反律」（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$ 為質數若且唯若

　
: $\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\geq 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 .$

本小節的公式未有任何實際用途。

## 其它等式

* 對於所有實數 _x_，有：

　
: $\left\lbrack {\frac {x}{2}}\right\rbrack ={\frac {1}{4}}((-1)^{[x]}-1+2[x])$

　
: $\left\lbrack {\frac {x}{3}}\right\rbrack ={\frac {-2}{\sqrt {3}}}\sin({\frac {2\pi }{3}}[x]+{\frac {\pi }{3}})+1$
* 設 _x_ 為一個實數，_n_ 為整數，則

　
: $\sum _{k=0}^{n-1}E(x+{\frac {k}{n}})=E(nx)$

　
: $E({\frac {1}{n}}E(nx))=E(x)$

* 對於兩個相反數的高斯符號，有：

　
: 如果 x 為整數，則 $E(x)+E(-x)=0$

　
: 否則 $E(x)+E(-x)=-1$

## 參考來源

* Crandall, Richard; Pomerance, Carl. Prime Numbers: A Computational Perspective. New York: Springer. 2001 [2022-02-06]. ISBN0-387-94777-9. （原始內容存檔於 2022-04-09）.
* Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete Mathematics. Reading Ma.: Addison-Wesley. 1994. ISBN 0-201-55802-5.
* Hardy, G. H.; Wright, E. M. An Introduction to the Theory of Numbers (Fifth edition). Oxford: Oxford University Press. 1980. ISBN 978-0-19-853171-5.
* Lemmermeyer, Franz. Reciprocity Laws: from Euler to Eisenstein. Berlin: Springer. 2000. ISBN 3-540-66957-4.
* Ribenboim, Paulo. The New Book of Prime Number Records. New York: Springer. 1996. ISBN 0-387-94457-5.