取整函数
在数学和计算机科学中，取整函数是一类将实数映射到相近的整数的函数。[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.