一个数的地板和天花板

一个实数的取整有两种方式，一是向下取整，fl(x)，称为floor of x （地板函数），即是x的整数部分，x = fl(x) + dp(x), 0 ≤ dp(x) < 1(x的小数部分)；另一个是向上取整，cl(x)，称为ceiling of x （天花板），即是x = cl(x) – cp(x)， 0 ≤ cp(x) < 1。当x为整数时，fl(x) = cl(x)；但x不是整数时，cl(x) = fl(x) + 1。dp(x)和cp(x)都是周期为1的函数；fl(x)和cl(x)都是非初等函数，不在任何国家的数学大纲内，却是数学竞赛出题者的最爱。

fl(x)的主要应用在于 “滤波”, 即在一种量的连续分布中，去掉某些成分后，剩余部分的数学表示。对于离散的有理数m/n，fl(m/n) 是正整数m除以正整数n的商，余数m%n (按C语言的记号) 自然就是 m – nfl(m/n) 。对任意实数x, 1/2 – dp(x)是可以用Fourier级数表示的，如果x非整数，它就等于sigma{sin(2πnx)/nπ, n从1加到无穷} 。

例如，有人把完全平方数从正整数列中去掉，得到2, 3, 5, 6, 7, 8, 10, …；它的第n项就是n + fl(sqrt(n))，若n ≤ fl^2(sqrt(n)) + fl(sqrt(n))；否则为n + 1 + fl(sqrt(n))。也可以把任意k次幂去掉，剩下的数用地板函数表出。也有人把正整数n重复n次排成一行：1, 2, 2, 3, 3, 3, 4, 4, 4, 4, …, 它的第n项就是fl(sqrt(2n) + 0.5), 也可以表示为fl[(1 + sqrt(8n – 7))/2]。在2011年的Euclid竞赛中的第九题，就是对此数列性质的讨论。

还有人把前n个自然数排成一圈（圆形），从1开始，按照顺时针方向，去一个留一个，最后被去掉的那个数记为L(n) （2022年Cayley Contest最后一题）。显然，L(1) = 1, 当n > 1时，第一轮过后剩下的是全部的偶数2, 4, …, 2fl(n/2) ；因此L(n) = 2L(fl(n/2)) ；自然有L(2k) = L(2k + 1)。这个递推式的解很简单，就是L(2^m + h) = 2^m，对所有非负整数h < 2^M。

在1996年的AIME，2005年的Euclid竞赛中，出题者把1到n的自然数排成一行，从1开始，从左到右，留一个去一个；然后再回过头来，从右到左，留一个去一个；如此反复，直到最后一个数。其编号记为R(n)。显然，R(1) = 1；R(2k – 1) = R(2k)。对于n = 2k，第一轮过后，剩下的是k个奇数：1, 3, …, 2k – 1；如果从右到左将它们重新编号，就可发现一个规律：[R(2k) + 1]/2 + R(k) = k + 1，即R(2k) = 2k + 1 – 2R(k)。写成一般式子，有R(n) = 2cl(n/2) + 1 – 2R(cl(n/2))。在AIME的那道题中，n = 1024是2的幂，很容易解出。对于一般的n，可以把它写为二进制数，得出递推公式。

另一个应用是计数：满足不等式g(n) ≤ x的正整数n的个数为fl(g^(-1)(x))。例如，在n!中，它能够被一个质数p除尽的最高次数为fl(n/p) + fl(n/p^2) + fl(n/p^3) + … 直到0.因此n! 末尾的 0的个数为fl(n/5) + fl(n/25) + fl(n/125) + fl(n/625) + …。计算此和式的办法是将n用p进位制表示，结果就是逐次去掉一个低位数字，依次把各位数字从低位到高位相加。

再一个应用是整除性的判定：正整数m被n整除就是dp(m/n) = (m%n)/n = 0。根据Wilson定理，一个数p为质数的充分必要条件是，dp{[(n – 1)! + 1]/n} = 0；但阶乘太大，难于计算。如果用平方根判别法，p为质数的条件是fl(p/q) 不等于0，对有质数q≤ sqrt(p)。给定前n个质数，可以用地板函数表示出下一个质数。

涉及到fl(x)的计算或证明，实际上都是解不等式。有兴趣的话，不妨试试这几给问题:

（1）给定正整数n. 问集合{fl(k^2/n): k = 1, 2, …, n}中，有多少个不同的整数值？

（2）解方程 fl(3/x) + fl(4/x) = 5；

（3）解方程xfl(x) = 7；

（4）给定正整数n，定义一个数列t(k) = 2n(k^2%n) + k，对k = 1, 2, …, n；请找出所有正整数n，使得有四个不同的正整数i, j, k, m ≤ n, 满足t(i) + t(j) = t(k) + t(m)。

最后一题是Euclid竞赛2017年的问题。在这个竞赛中，许多问题都没有一个初等函数表达式。但是，如果能够使用地板/天花板的话，则只剩计数问题难以表出了。时至今日（3月7日），离此项竞赛还有一个月的时间，若能弄清表达式的话，一定满分可达！