取整函數
在數學和電腦科學中，取整函數是一類將實數對映到相近的整數的函數。[1]
常用的取整函數有兩個，分別是下取整函數（英語：floor function）和上取整函數（ceiling function）。
下取整函數即為取底符號，在數學中一般記作<math>[ x ]</math>或者<math>\lfloor x \rfloor</math>或者<math>E(x)</math>，在電腦科學中一般記作floor(x)，表示不超過x的整數中最大的一個。
- <math> [ x ]=\max\, \{n\in\mathbb{Z}\mid n\le x\}.</math>
舉例來說，<math>[ 3.633 ] = 3</math>，<math>[ 56 ] = 56</math>，<math>[ -2 ] = -2</math>，<math>[ -2.263 ] = -3</math>。對於非負的實數，其下取整函數的值一般叫做它的整數部分或取整部分。而<math>x -[ x]</math>叫做x的小數部分。每個分數都可以表示成其整數部分與一個真分數的和，而實數的整數部分和小數部分是與此概念相應的拓延。
下取整函數的符號用方括號表示（<math>[x]</math>），稱作高斯符號，首次出現是在卡爾·弗里德里希·高斯的數學著作《算術研究》。
上取整函數即為取頂符號在數學中一般記作<math>\lceil x \rceil</math>，在電腦科學中一般記作ceil(x)，表示不小於x的整數中最小的一個。
- <math> \lceil x \rceil=\min\{n\in\mathbb{Z}\mid x\le n\}.</math>
舉例來說，<math>\lceil 3.633 \rceil = 4</math>，<math>\lceil 56 \rceil = 56</math>，<math>\lceil -2 \rceil = -2</math>，<math>\lceil -2.263 \rceil = -2</math>。
電腦中的上取整函數和下取整函數的命名來自於英文的ceiling（天花板）和floor（地板），1962年由肯尼斯·艾佛森於《A Programming Language》引入。[2]
性質[編輯]
對於高斯符號，有如下性質。
- 按定義：
- <math> [ x] \le x < [ x ] + 1</math>; 當且僅當 <math>x</math> 為整數時取等號。
- 設 <math>x</math> 和 <math>n</math> 為正整數，則：
- <math> \left[ \frac{n}{x} \right] \geq \frac{n}{x} - \frac{x-1}{x} </math>
- 當 <math>n</math> 為正整數時，有：
- <math> \left[ \frac{x}{n} \right] = \frac{x-x\bmod n}{n},</math> 其中 <math>x \bmod n</math> 表示 <math>x</math> 除以 <math>n</math> 的餘數。
- 對任意的整數 <math>k</math> 和任意實數 <math>x</math>，
- <math> [ {k+x} ] = k + [ x].</math>
- 一般的數值修約規則可以表述為將 <math>x</math> 對映到 <math>\left[ x + 0.5 \right]</math>；
- 高斯符號不是連續函數，但是上半連續的。作為一個分段的常數函數，在其導數有定義的地方，高斯符號導數為零。
- 設 <math>x</math> 為一個實數，<math>n</math> 為整數，則由定義，<math>n \leq x</math> 當且僅當 <math>n \leq \left[ x\right] </math>。
- 當 <math>x</math> 是正數時，有：
- <math>\left[ 2 x \right] - 2 \left[ x \right] \leqslant 1</math>
- 用高斯符號可以寫出若干個質數公式，但沒有什麼實際價值，見§ 質數公式。
- 對於非整數的 <math>x</math>，高斯符號有如下的傅立葉級數展開：
- <math>[ x] = x - \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^\infty \frac{\sin(2 \pi k x)}{k}.</math>
- 根據Beatty定理，每個正無理數都可以通過高斯符號製造出一個整數集的分劃。
- 最後，對於每個正整數 <math>k</math>，其在 p 進制下的表示有 <math>[ \log_{p}(k) ] + 1</math> 個數碼。
函數間之關係[編輯]
由上下取整函數的定義，可見
- <math>\lfloor x \rfloor \le \lceil x \rceil,</math>
等號當且僅當<math>x</math>為整數，即
- <math>\lceil x \rceil - \lfloor x \rfloor = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}</math>
實際上，上取整與下取整函數作用於整數<math>n</math>，效果等同恆等函數：
- <math>\lfloor n \rfloor = \lceil n \rceil = n.</math>
自變量加負號，相當於將上取整與下取整互換，外面再加負號，即：
- <math> \begin{align}
\lfloor x \rfloor +\lceil -x \rceil &= 0, \\ -\lfloor x \rfloor &= \lceil -x \rceil, \\ -\lceil x \rceil &= \lfloor -x \rfloor. \end{align} </math>
且：
- <math>\lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\ -1,&\text{ 若 }\ x\not\in \mathbb{Z}, \end{cases}</math>
- <math>\lceil x \rceil + \lceil -x \rceil = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}</math>
至於小數部分<math>\{x \} = x - \lfloor x \rfloor</math>，自變量取相反數會使小數部分變成關於1的「補碼」：
- <math>\{ x \} + \{ -x \} = \begin{cases}
0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}</math>
上取整、下取整、小數部分皆為冪等函數，即函數疊代兩次的結果等於自身：
- <math>
\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} </math>
而多個上取整與下取整依次疊代的效果，相當於最內層一個：
- <math>
\begin{align} \Big\lfloor \lceil x \rceil \Big\rfloor &= \lceil x \rceil, \\ \Big\lceil \lfloor x \rfloor \Big\rceil &= \lfloor x \rfloor, \end{align} </math> 因為外層取整函數實際衹作用在整數上，不帶來變化。
商[編輯]
若<math>m</math>和<math>n</math>為正整數，且<math>n \neq 0</math>，則
- <math>0 \le \left \{\frac{m}{n} \right\} \le 1-\frac{1}{|n|}.</math>
若<math>n</math>為正整數，則[3]
- <math>\left\lfloor\frac{x+m}{n}\right\rfloor = \left\lfloor\frac{\lfloor x\rfloor +m}{n}\right\rfloor,
</math>
- <math>\left\lceil\frac{x+m}{n}\right\rceil = \left\lceil\frac{\lceil x\rceil +m}{n}\right\rceil.
</math>
若<math>m</math>為正數，則[4]
- <math>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,
</math>
- <math>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.
</math>
代<math>m = 2</math>，上式推出：
- <math>n= \left\lfloor \frac{n}{2}\right \rfloor + \left\lceil\frac{n}{2}\right \rceil.</math>
更一般地，對正整數<math>m</math>，有埃爾米特恆等式：[5]
- <math>\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,
</math>
- <math>\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.
</math>
對於正整數<math>m</math>，以下兩式可將上下取整函數互相轉化：[6]
- <math>\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, </math>
- <math>\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. </math>
對任意正整數<math>m</math>和<math>n</math>，有：[7]
- <math>\sum_{k = 1}^{n - 1} \left\lfloor \frac{k m}{n} \right\rfloor = \frac{(m - 1)(n - 1)+\gcd(m,n)-1}2,</math>
作為特例，當<math>m</math>和<math>n</math>互質時，上式簡化為
- <math>\sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor = \frac{1}{2}(m - 1)(n - 1).</math>
此等式可以幾何方式證明。又由於右式關於<math>m</math>、<math>n</math>對稱，可得
- <math>\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. </math>
更一般地，對正整數<math>m, n</math>，有
- <math>\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} </math>
上式算是一種「互反律」（reciprocity law）[7]，與§ 二次互反律有關。
應用[編輯]
二次互反律[編輯]
高斯給出二次互反律的第三個證明，經艾森斯坦修改後，有以下兩個主要步驟。[8][9]
設<math>p</math>、<math>q</math>為互異奇質數，又設
- <math>m = \frac{p - 1}{2},</math> <math>n = \frac{q - 1}{2}.</math>
- <math>\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 },</math>
同樣
- <math>\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 }.</math>
其後，採用幾何論證，證明
- <math>\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. </math>
總結上述兩步，得
- <math>\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{mn}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.</math>
此即二次互反律。一些小整數模奇質數<math>p</math>的二次特徵標，可以高斯符號表示，如：[10]
- <math>\left(\frac{2}{p}\right) = (-1)^{\left\lfloor\frac{p+1}{4}\right\rfloor},</math>
- <math>\left(\frac{3}{p}\right) = (-1)^{\left\lfloor\frac{p+1}{6}\right\rfloor}.</math>
質數公式[編輯]
下取整函數出現於若干刻畫質數的公式之中。舉例，因為<math>\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor</math>在<math>m</math>整除<math>n</math>時等於<math>1</math>，否則為<math>0</math>，所以正整數<math>n</math>為質數當且僅當[11]
- <math>\sum_{m=1}^{\infty}\left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right) = 2.</math>
除表示質數的條件外，還可以寫出公式使其取值為質數。例如，記第<math>n</math>個質數為<math>p_n</math>，任選一個整數<math>r > 1</math>，然後定義實數<math>\alpha</math>為
- <math>\alpha = \sum_{m=1}^\infty p_m r^{-m^2}.</math>
則衹用取整、冪、四則運算可以寫出質數公式：[12]
- <math>p_n = \left\lfloor r^{n^2}\alpha \right\rfloor - r^{2n-1}\left\lfloor r^{(n-1)^2}\alpha\right\rfloor.</math>
類似還有米爾斯常數<math>\theta = 1.3064\ldots</math>，使
- <math>\left\lfloor \theta^3 \right\rfloor, \left\lfloor \theta^9 \right\rfloor, \left\lfloor \theta^{27} \right\rfloor, \dots</math>
皆為質數。[13]
若不疊代三次方函數，改為疊代以<math>2</math>為㡳的指數函數，亦有<math>\omega = 1.9287800\ldots</math>使
- <math>\left\lfloor 2^\omega\right\rfloor, \left\lfloor 2^{2^\omega} \right\rfloor, \left\lfloor 2^{2^{2^\omega}} \right\rfloor, \dots</math>
皆為質數。[13]
以質數計算函數<math>\pi(x)</math>表示小於或等於<math>x</math>的質數個數。由威爾遜定理，可知[14]
- <math>\pi(n) = \sum_{j=2}^n\left\lfloor\frac{(j-1)!+1}{j} - \left\lfloor\frac{(j-1)!}{j}\right\rfloor\right\rfloor.</math>
又或者，當<math>n \ge 2</math>時：[15]
- <math>\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.</math>
其它等式[編輯]
- 對於所有實數x，有：
- <math> \left\lfloor \frac{x}{2} \right\rfloor = \frac{1}{4} ((-1)^{\lfloor x \rfloor}-1 + 2 \lfloor x \rfloor ) </math>
- <math> \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 )</math>
參考來源[編輯]
- ^ Ronald Graham, Donald Knuth and Oren Patashnik. "Concrete Mathematics". Addison-Wesley, 1999. Chapter 3, "Integer Functions".
- ^ Iverson, Kenneth E. A Programming Language. Wiley. 1962.
- ^ Graham, Knuth & Patashnik 1994，第73頁.
- ^ Graham, Knuth & Patashnik 1994，第85頁.
- ^ Graham, Knuth & Patashnik 1994，p. 85 and Ex. 3.15.
- ^ Graham, Knuth & Patashnik 1994，Ex. 3.12.
- ^ 7.0 7.1 Graham, Knuth & Patashnik 1994，第94頁.
- ^ Lemmermeyer 2000，§ 1.4, Ex. 1.32–1.33.
- ^ Hardy & Wright 1980，§§ 6.11–6.13.
- ^ Lemmermeyer 2000，第25頁.
- ^ Crandall & Pomerance 2001，Ex. 1.3, p. 46，求和式的上限<math>\infty</math>可以換成<math>n</math>。尚有一個等價的表述：<math>n > 1</math>為質數當且僅當<math>\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.</math>
- ^ Hardy & Wright 1980，§ 22.3.
- ^ 13.0 13.1 Ribenboim 1996，第186頁
- ^ Ribenboim 1996，第181頁.
- ^ Crandall & Pomerance 2001，Ex. 1.4, p. 46.
- ^ Ribenboim 1996，第180頁（譯文）：「雖然該些公式毫不實用⋯⋯但邏輯學家希望清晰明白不同公理體系，如何推導出算術各方面，則或許與此有關⋯⋯」
- ^ Hardy & Wright 1980，第344—345頁（譯文）：「若數<math>\alpha</math>的準確值⋯⋯可以無關質數的方式表達，則該些公式之任一（或一切類似公式）的地位將截然不同。似乎沒有此種可能，但卻不能完全排除。」
- Crandall, Richard; Pomerance, Carl. Prime Numbers: A Computational Perspective. New York: Springer. 2001 [2022-02-06]. ISBN 978-0-387-94777-8. （原始內容存檔於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 978-3-540-66957-9.
- Ribenboim, Paulo. The New Book of Prime Number Records. New York: Springer. 1996. ISBN 978-0-387-94457-9.